题意：给出a,b,n计算f(a^b)%n的值，其中f(i)=f(i-2)+f(i-1)
学习的紫书，自己做的时候想的是，每次输入一个n,再打表找，
后来看了标程，发现是用一个二维数组直接就将不同的n对应的周期存储下来了
另外还要注意的是0的任何次方为0
还有找周期的时候，第一次看的时候不理解， 后来觉得应该是这样的
一个数模上n的余数有n种 0,1,2,3,4，---，n-1共n种
然后在前n*n个数里面，可以每一种余数分配n个数，所以就是n*n个数，当再多一个数的时候一定就会重复了
1 #include<iostream> 2 #include<cstdio> 3 #include<cstring> 4 #include <cmath> 5 #include<stack> 6 #include<vector> 7 #include<map> 8 #include<set> 9 #include<queue> 10 #include<algorithm> 11 using namespace std; 12 13 typedef long long LL; 14 typedef unsigned long long ULL; 15 const int INF = (1<<30)-1; 16 const int mod=1000000007; 17 const int maxn=1005; 18 19 int f[maxn][6*maxn],p[maxn]; 20 21 int pow_mod(ULL a,ULL b,int n){ 22 if(b==0) return 1; 23 int k=pow_mod(a,b/2,n); 24 k=k*k%n; 25 if(b%2==1) k= k * a % n; 26 return k; 27 } 28 29 int solve(ULL a,ULL b,int n){ 30 if(a==0||n==1) return 0;//0的 任意次方为0，一个数模上1的余数为0 31 int idx=pow_mod(a%p[n],b,p[n]) ; 32 return f[n][idx]; 33 } 34 35 int main(){ 36 int ncase; 37 int n; 38 for(int n=2;n<=1000;n++){ 39 f[n][0]=0;f[n][1]=1; 40 for(int i=2;;i++){ 41 f[n][i]=(f[n][i-2]+f[n][i-1])%n; 42 if(f[n][i-1]==0&&f[n][i]==1){ 43 p[n]=i-1; 44 break; 45 } 46 } 47 } 48 // freopen("in.txt","r",stdin); 49 // freopen("out.txt","w",stdout); 50 scanf("%d",&ncase); 51 while(ncase--){ 52 ULL a,b; 53 54 cin>>a>>b>>n; 55 cout<<solve(a,b,n)<<" "; 56 } 57 return 0; 58 }