程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> SDUT 2568 小白學Fibonacci之一

SDUT 2568 小白學Fibonacci之一

編輯:C++入門知識

題目描述 一天,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;   }    

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved