題目描述 一天，Z懂得了Fibonacci數列，發現數列有以下規律： F[1]=F[2]=1; F[N]=F[N-1]+F[N-2]; 於是Z覺得很神奇，想知道任意兩個Fibonacci數有沒有大於1的公約數。但是光在有限的范圍內手算還不行，於是Z找到了你，希望你能幫忙編個程序算算。 任務：指定兩個Fibonacci數的項數（也就是這兩個數各是第幾項），求出這兩個數的最大公約數。 例如輸入3 6，輸出2（因為GCD(F[3],F[6])=2）。 輸入 多組數據，每行兩個數A，B。到文件末尾。 0<A,B<100007 輸出 每組數據輸出一行。保證最後結果不超過2^64-1，所以使用64位無符號整數。 示例輸入 30 15 14 28 12 24 17 17 30 6 24 24 20 10 24 12 29 29 9 18 示例輸出 610 377 144 1597 8 46368 55 144 514229 34 這道題目剛開始看到的時候我想的是輾轉相減求公約數。 因為斐波那契是和的形式，於是我想用減法求公約數可以，可是實際劃了一下，不可以，因為數太大了。 接著又想到一一枚舉。 將這題轉換成大數求余數，這個很容易處理。 劃了一下還是不行，因為，要枚舉1到2的60多次方，除非是用二分。 否則肯定會死的很慘，而這題又用不上。所有就不知道怎麼處理了。 最後想到找規律，畫了畫斐波那契數列，果然存在著規律，發現： 如果一個斐波那契數是n，是第x個數，那麼數n與第x+x，x+2*x,x+3*x....個的最大公約數就是n。根據這個規律就能做出這道題目來 [cpp] #include <stdio.h> #include <string.h> #include <math.h> int main() { unsigned long long int res1,res2,res,max; int i,j,n,m,s,t,pre; int l,r; while(scanf("%d %d",&l,&r)!=EOF) { if(l>r) { t=l; l=r; r=t; } if(l==1||l==2||r==1||r==2) { printf("1\n"); continue; } res1=1; res2=1; res=1; if(l==r) { for(i=3;i<=l;i++) { res=res1+res2; res1=res2; res2=res; } printf("%llu\n",res); continue; } max=1; pre=1; for(i=3;i<=l; i+=pre) { if((l%i==0)&&(r%i==0)) { pre=i; max=i; } } res1=1; res2=1; res=1; for(i=3;i<=max;i++) { res=res1+res2; res1=res2; res2=res; } printf("%llu\n",res); } return 0; }
