链接：
https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=2629
题意：
输入两个非负整数a、b和正整数n（0≤a,b<2^64，1≤n≤1000），你的任务是计算f(a^b)除以n的余数。
其中f(0)=0,f(1)=1，且对于所有非负整数i，f(i+2)=f(i+1)+f(i)。
分析：
所有计算都是对n取模的，设F(i)=f(i)%n。不难发现，当二元组(F(i), F(i+1))出现重复时，整个序列就开始重复。
多久会出现重复呢？因为余数最多n种，所以最多n*n项就会出现重复。实际测试出最多3001项左右就会出现重复。
所以只需计算出周期，然后算出F(a^b)对应于其中的哪一项即可。
代码：
#include <cstdio> typedef unsigned long long ULL;
const int UP = + ;
int f[UP][UP*], period[UP]; int qmod(ULL a, ULL b, ULL n) { // 快速幂模
a %= n;
ULL res = ;
while(b) {
if(b & ) res = res * a % n;
b >>= ;
a = a * a % n;
}
return res;
} int main() {
period[] = ;
for(int n = ; n <= ; 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;
}
}
} int T, n;
ULL a, b;
scanf("%d", &T);
while(T--) {
scanf("%llu%llu%d", &a, &b, &n);
int p = qmod(a, b, period[n]);
printf("%d\n", f[n][p]);
}
return ;
}