题目
题目大意
输入两个非负整数\(a\)、\(b\)和正整数\(n\)(\(0 ≤ a, b ＜
{2}^{64}\), \(1 ≤ n ≤ 100\)),
你的任务是计算\(f({a}^{b})\)除以\(n\)的余数。其中\(f(0) = f(1) = 1\), 且对于所有非负整数\(i\), \(f(i + 2) =
f(i + 1) + f(i)\)。
题解
这道题大概就用到了斐波那契循环节(几个月之前我搜的时候还只有两篇博客现在突然多了起来)
所有计算都是对\(n\)取模的,
不妨设\(F(i) = f(i)\ mod\
n\)。不难发现, 根据递推公式, 当二元组\((F(i), F(i + 1))\)出现重复时，
整个序列就开始重复。
因此递推\(F(i)\)直到出现二元组\((1, 1)\)时就会从头开始重复,
此时序列中就已经有\(f({a}^{b})\ mod\
n\)的值了,
而我们只需要像做一些数列找规律的数学题就能够得到答案了, 当然计算\(a^b\)会用到快速幂。
还有一点, 数据范围超过了long long的上限,
需要用unsigned long long,
如果用scanf或printf则需要用到"%llu"(不是"%ull")。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| #include <iostream>
#include <cstdio>
int Fibonacci[1000010];
int Mod;
int QuickPower(register unsigned long long base,register unsigned long long times,const int &kMod) {
register unsigned long long ret(1);
base %= kMod;
while (times) {
if (times & 1) ret *= base, ret %= kMod;
base = base * base % kMod;
times >>= 1;
}
return ret;
}
int main(int argc, char const *argv[]) {
register int T;
register unsigned long long a,b;
scanf("%d", &T);
while (T--) {
scanf("%llu %llu %d",&a, &b, &Mod);
if (Mod == 1 || !a) {
puts("0");
continue;
}
Fibonacci[0] = Fibonacci[1] = 1;
register int p(1);
for (register int i(2); ; ++i) {
Fibonacci[i] = (Fibonacci[i - 1] + Fibonacci[i - 2]) % Mod;
if (Fibonacci[i] == 1 && Fibonacci[i - 1] == 1) {
p = i - 1;
break;
}
}
printf("%d\n", Fibonacci[QuickPower(a, b, p) - 1]);
}
return 0;
}
|