1 000 000 000 000 000 000個Fibonacci數

-1

的問題是獲得在1,000,000,000,000,000,000th Fibonacci數％百萬
1 000 000 000 000 000 000個Fibonacci數

#include <iostream> 
#define fibo(a,b) {long long c=b;b=a;a=(b+c)%1000000;} 

using namespace std; 

int main(){ 
    long long a=1,b=0;  //two num 
    long long pa,pb,n,k,arr[2][1000]; //last two num,input,input<=2^k 
    cin>>n; 
    arr[0][0]=n/2;arr[1][0]=n%2; 
    for(unsigned long long i=1;n>3;i++){ 
     arr[0][i]=arr[0][i-1]/2; 
     arr[1][i]=arr[0][i-1]%2; 
     if(arr[0][i]==1){ 
      k=i; 

      break; 
     } 
    } 
    if(n<=3){  //special occasions 
     switch(n){ 
      case 0:cout<<"0"<<endl;break; 
      case 3:cout<<"2"<<endl;break; 
      default:cout<<"1"<<endl; 
     } 
     return 0; 
    } 
    while(k>=0){ //calc 
     pa=a;pb=b; 
     a=((pa+pb*2)*pa)%1000000;  //F(2n)=(F(n)+F(n-1)*2)*F(n) 
     b=(pa*pa+pb*pb)%1000000;  //F(2n-1)=F(n)^2+F(n-1)^2 
     if(arr[1][k--]==1){fibo(a,b);} //F(n+1)=F(n)+F(n-1) 

    } 
    cout<<a<<endl; 
    return 0; 
}

當它錯了嗎？爲什麼它錯了？
我找不到不同的場合。

來源

2016-09-24 stoad

第n個斐波納契數有一個[封閉形式方程]（https://en.wikipedia.org/wiki/Fibonacci_number#Closed-form_expression） - 沒有必要全部計算它們。 –

感謝回答，但我需要整數，而不是浮動 – stoad

這是第n個斐波納契數的公式，一個非常定義的整數。我完全不知道你的評論意味着什麼。 –

您可以考慮在這裏使用的替代方法是Fibonacci數字只剩下1,000,000個可能的餘數，因此如果您要計算第一個1,000,001斐波納契數字，在某些時候您會發現數字會開始進入一個循環。因此請考慮以下方法：

計算第一個1,000,001斐波納契數。
這些數字最終會進入一個循環。確定進入循環需要多少步驟k以及循環的時間。
可以通過確定1,000,000,000,000,000,000次斐波納契數在循環中的位置（（1,000,000,000,000,000,000,000k）％）位置來找到1,000,000,000,000,000,000000000000000000000的斐波納契數，模數1,000,000。所以看看那個位置並在那裏輸入條目。

來源

2017-07-21 21:17:59 templatetypedef

1 000 000 000 000 000 000個Fibonacci數

回答

相關問題