TLE-oj Cup Round 10 - Hàm số
Xem PDF
Nộp bài
Điểm:
900 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
128M
Input:
FUNCTION.inp
Output:
FUNCTION.out
Tác giả:
Dạng bài
NguyenHuuNhatQuang có hai hàm f(x, y, k) và g(a, b, c, k) được định nghĩa như sau (với div là phép chia lấy nguyên, mod là phép chia lấy dư và * là phép nhân):
định nghĩa g(a, b, c, k):
nếu b = 0:
nếu c = 0:
trả về a.
ngược lại:
trả về g(a, 1, 0, k).
ngược lại:
nếu a = 0:
nếu c = 0:
trả về b.
ngược lại
trả về g(1, b, 0, k).
ngược lại:
nếu a mod k + b mod k + c >= k:
đặt t = g(a div k, b div k, 1, k)
ngược lại:
đặt t = g(a div k, b div k, 0, k)
trả về t * k + ((a + b + c) mod k).
định nghĩa f(a, b, k):
nếu b = 0:
trả về 0.
ngược lại:
đặt t = f(a, b div 2, k)
nếu b mod 2 = 1:
trả về g(t * 2, a, 0, k).
ngược lại:
trả về t * 2.
Cài đặt đoạn mã giả trên bằng C++
long long g(long long a, long long b, long long c, long long k) {
if (b == 0) {
if (c == 0) {
return a;
} else {
return g(a, 1, 0, k);
}
} else {
if (a == 0) {
if (c == 0) {
return b;
} else {
return g(1, b, 0, k);
}
} else {
if (a % k + b % k + c >= k) {
long long t = g(a / k, b / k, 1, k);
return t * k + ((a + b + c) % k);
} else {
long long t = g(a / k, b / k, 0, k);
return t * k + ((a + b + c) % k);
}
}
}
}
long long f(long long a, long long b, long long k) {
if (b == 0) {
return 0;
} else {
long long t = f(a, b / 2, k);
if (b % 2 == 1) {
return g(t * 2, a, 0, k);
} else {
return t * 2;
}
}
}
Nhiệm vụ của bạn rất đơn giản, đó là đếm xem với hai số nguyên dương n, k cho trước, có bao nhiêu cặp số nguyên dương (a, b) sao cho a \le b \le n và f(a, b, k) = n.
Input, Output và Subtasks
Input: (FUNCTION.inp)
- Một dòng duy nhất gồm hai số nguyên dương n, k (1 < n, k \le 10^{14}).
Output: (FUNCTION.out)
- In ra kết quả bài toán. Vì kết quả có thể rất lớn nên chỉ cần lấy số dư của nó khi chia cho 10^9 + 7.
Subtasks
- Subtask 1 (60\%): n \le 2000.
- Subtask 2 (40\%): Không có giới hạn gì thêm.
Sample
Input (FUNCTION.inp)
2 2
Output (FUNCTION.out)
1
Note
- Không có note.
Bình luận