评测地址：http://acm.hust.edu.cn/vjudge/problem/41990
The i'th Fibonacci number f (i) is recursively de ned in the following way: f () = and f () = f (i + ) = f (i + ) + f (i) for every i Your task is to compute some values of this sequence. Input Input begins with an integer t
; , the number of test cases. Each test case consists of three in-tegers a, b, n where a; b < (a and b will not both be zero) and n . Output For each test case, output a single line containing the remainder of f (ab) upon division by n. Sample Input Sample Output
题目文本
题目大意：
输入两个非负整数a,b和正整数n（0<=a,b<2^64,1<=n<=1000)，你的任务是计算f(a^b)除以n的余数。其中f(0)=f(1)=1，且对于所有非负整数i，f(i+2)=f(i+1)+f(i)。
解题思路：
这么大的数字，直接算是不现实的。
此时我们会想，要是f(i)% n能出现循环多好啊。
我们取F(i)=f(i) % n。若(F(i-1),F(i))出现重复，则整个序列将开始重复。 比如n=3时 1，1，2，0，2，2，1，0，1，1，2，0，2，2… 因为余数最多有n种可能，所以最多到第n^2项，就会出现重复，开始循环。 所以我们先花至多O(n^2)的时间处理一下找到循环节，再判断一下F(a^b)具体等于哪一项即可。
AC代码：
#include<cstdio>
#include<iostream>
#define ll unsigned long long
using namespace std;
const int N=1e6+;
int T,n,mod,f[N]={,,};
ll a,b;
int kpow(ll a,ll p){
int ans=;
for(;p;p>>=,a=(a*a)%mod) if(p&) ans=(ans*a)%mod;
return ans;
}
int main(){
cin>>T;
while(T--){
cin>>a>>b>>n;
if(n==||!a){printf("0\n");continue;}
for(int i=;i<=n*n+;i++){
f[i]=(f[i-]+f[i-])%n;
if(f[i]==f[]&&f[i-]==f[]){mod=i-;break;}
}
printf("%d\n",f[kpow(a%mod,b)]);
}
return ;
}