这题花了我一天时间调，还是自己渣，很多细节都没注意。
因为要求的是 f(ab) mod n ，那么就可以设F(i)=f(i) mod n 。则f(ab) mod n=F(ab) 。 这里有一个关键的地方， f(i) mod n 会重复循环，为什么会这样呢？因为斐波那契数列的每一项都只和前两项有关。所以共有 n2 个可能，最后一定会出现循环节，也就是说余数最多 n 种，则最多 n2 项就会出现重复。
这下就可以先建一个 F(i) 的表：因为根据斐波那契数列递推式：
f(i)=f(i−1)+f(i−2) //式1根据式1和 (a+b) mod n=(a mod n+b mod n) mod n 得出
f(i) mod n=(f(i−1) mod n+f(i−2) mod n) mod n //式2
而F(i)=f(i) mod n //式3
则根据式2和式3得出
F(i)=(f(i−1) mod n+f(i−2) mod n) mod n=(F(i−1)+F(i−2)) mod n即 F(i) 通过 F(i−1) 和 F(i−2) 求和取模得出。关键是需要找到重复节的位置，并停止填表。 最后找到 ab 的位置，查表即可。
代码如下：
void Fibonacci_F() { F[0] = 0; F[1] = 1; for(int i=2; ; i++) { F[i] = (F[i-1] + F[i-2]) % n; if(F[i-1] == 0 && F[i] == 1) { k = i-1; break; } } return; }完整代码如下：
#include<cstdio> #include<iostream> using namespace std; typedef unsigned long long LL; const int maxn = 10000000+10; int F[maxn]; LL a,b; int n,k; /*建表*/ void Fibonacci_F() { F[0] = 0; F[1] = 1; for(int i=2; ; i++) { F[i] = (F[i-1] + F[i-2]) % n; if(F[i-1] == 0 && F[i] == 1) { k = i-1; break; } } return; } /*幂求模*/ int pow_mod(LL a, LL b, int n) { if(b == 0) return 1; int x = pow_mod(a, b/2, n); x = x * x % n; if(b%2 == 1) x = x * a % n; return x; } int main() { int T; scanf("%d",&T); while(T--) { cin>>a>>b>>n; if(a == 0 || n == 1) { cout<<0<<endl;//关键。 } else{ Fibonacci(); printf("%d\n",F[pow_mod(a%k,b,k)]); } } return 0; }有一个细节很重要：
if(a == 0 || n == 1) { cout<<0<<endl;//关键。 }就是因为少了这个，我一直runtime error，所以细节决定成败。
