题意：
斐波那契数列f(0) = 0, f(1) = 1, f(n+2) = f(n+1) + f(n) (n ≥ 0)
输入a、b、n，求f(ab)%n
分析：
构造一个新数列F(i) = f(i) % n，则所求为F(ab)
如果新数列中相邻两项重复出现的话，则根据递推关系这个数列是循环的。
相邻两项所有可能组合最多就n2中，所以根据抽屉原理得到这个数列一定是循环的。
求出数列的周期，然后快速幂取模即可。
#include <cstdio>
#include <iostream>
using namespace std; const int maxn = + ;
typedef unsigned long long ULL;
int f[maxn][maxn * ], period[maxn]; int pow_mod(ULL a, ULL b, int n)
{
if(b == ) return ;
int k = pow_mod(a, b/, n);
k = k * k % n;
if(b % == ) k = k * a % n;
return k;
} int solve(ULL a, ULL b, int n)
{
if(a == || n == ) return ;
int p = pow_mod(a % period[n], b, period[n]);
return f[n][p];
} int main(void)
{
freopen("11582in.txt", "r", stdin);
for(int n = ; n < maxn; ++n)
{
f[n][] = , f[n][] = ;
for(int i = ; ; ++i)
{
f[n][i] = (f[n][i-] + f[n][i-]) % n;
if(f[n][i-] == && f[n][i] == )
{
period[n] = i - ;
break;
}
}
} ULL a, b;
int n, T;
scanf("%d", &T);
while(T--)
{
cin >> a >> b >> n;
printf("%d\n", solve(a, b, n));
} return ;
}
代码君