大一刚开始接触ACM就买了《算法竞赛入门经典》这本书，当时只能看懂前几章，而且题目也没做，粗鄙地以为这本书不适合自己。等到现在快大三了再回过头来看，发现刘老师还是很棒的！
扯远了。。。
题意：问f[a^b]%n的值，f为斐波那契数。根据f[i]=f[i-1]+f[i-2]不难发现，当二元组(f[i],f[i-1])出现重复时，整个序列就开始重复了。如n=3，序列f[i]的前10项为
0，1，1，2，0，2，2，1，0，1
f[9]和f[10]与前两项一样。
那么周期会在哪出现呢？从n项中取2项为C(n,2)，即最多有n*(n-1)/2种组合，最多n^2，2<=n<=1000。实际上远小于n^2。
此时找到了周期长度m，答案为f[(a^b)%m]，a^b用快速幂解决。
坑点，2^64得用usingned long long存，格式是%llu；注意n=1时要输出0。
代码：
#include<stdio.h>
#include<string.h>
typedef unsigned long long ll;
ll a,b;
int n,m,f[*];
int pow(ll a,ll b,int mod){
int ans=;
while(b){
if(b&) ans=(ans*a)%mod;
a=(a*a)%mod;
b>>=;
}
return ans;
}
int main(){ int t;
scanf("%d",&t);
while(t--){
scanf("%llu%llu%d",&a,&b,&n);
f[]=,f[]=%n;
for(int i=;;i++){
f[i]=f[i-]+f[i-];
f[i]%=n;
if(f[i]==f[]&&f[i-]==f[]){
m=i-;
break;
}
}
int t=pow(a%m,b,m);
printf("%d\n",f[t]);
}
return ;
}