https://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&category=&problem=2629&mosmsg=Submission+received+with+ID+16978519
我们是要计算 f(a^b)%n
根据式子 f(i)=f(i-1)+f(i-2) f(i)%n=(f(i-1)%n+f(i-2)%n;
余数最多有n种，所以f(i)的周期会在n*n之内出现，假设周期为T f(a^b)=f(a^b%T)
另外需要注意题目的范围是 0 ≤ a, b < 2^64 应该使用 unsigned long long
还有处理n=1的情况，因为此时T并没有计算；
顺便给出以下数据类型的范围
unsigned int 0～4294967295
int 2147483648～2147483647
unsigned long 0～4294967295
long 2147483648～2147483647
long long的最大值：9223372036854775807
long long的最小值：-9223372036854775808
unsigned long long的最大值：18446744073709551615
__int64的最大值：9223372036854775807
__int64的最小值：-9223372036854775808
unsigned __int64的最大值：18446744073709551615
只不过我现在还没有弄懂一个地方 为什么要mod(a%T,b,T) 而不是 mod(a,b,T)??
#include<iostream> #include<string> #include<string> #include<string.h> #include<stdio.h> #include<queue> #include<math.h> #include<vector> #include<stdlib.h> #include<algorithm> #define maxn 1000010 using namespace std; typedef unsigned long long ULL; int f[maxn]; int n; ULL a,b; int mod(ULL x,ULL y,int mod){ int ans = 1; while(y){ if(y & 1) {ans = (int)((ans * x) % mod);} x = (x * x) % mod; y >>= 1; } return ans; } int main(){ int t,T; memset(f,0,sizeof(f)); f[0]=0;f[1]=1; cin>>t; while(t--){ cin>>a>>b>>n; if(a == 0 || n == 1) printf("0\n"); else{ for(int i=2;i<=n*n;i++){ f[i]=(f[i-1]+f[i-2])%n; if(f[i]==1&&f[i-1]==0){ T=i-1; break; } } int e=mod(a%T,b,T); cout<<f[e]<<endl; } } return 0; }
原文：http://www.cnblogs.com/wintersong/p/5258221.html