UVA 11582 Colossal Fibonacci Numbers!【數學】

大一剛開始接觸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[1111*1111];
int pow(ll a,ll b,int mod){int ans=1;while(b){if(b&1)    ans=(ans*a)%mod;a=(a*a)%mod;b>>=1;}return ans;
}
int main(){int t;scanf("%d",&t);while(t--){scanf("%llu%llu%d",&a,&b,&n);f[0]=0,f[1]=1%n;for(int i=2;;i++){f[i]=f[i-2]+f[i-1];f[i]%=n;if(f[i]==f[1]&&f[i-1]==f[0]){m=i-1;break;}}int t=pow(a%m,b,m);printf("%d\n",f[t]);}return 0;
} 

?