1 000 000 000 000 000 000 번째 피보나치 수

Question

문제는 1,000000000000000000th 피보나치 번호 % 1,000,000

#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; 
} 

가 잘못에서 얻을입니까? 왜 잘못 되었나요?
다른 경우를 찾을 수 없습니다.

Answer 1

여기에서 사용할 수있는 다른 방법은 피보나치 수에 대한 가능한 잉여 값이 1,000,000에 불과하다는 것입니다. 따라서 처음 1000,001 피보나치 수를 계산하는 경우 어떤 시점에서 숫자가 한순간에 들어 가라. 따라서 다음 접근법을 고려하십시오.

• 첫 번째 1,000,001 피보나치 수를 계산하십시오.
• 숫자가 결국주기를 입력합니다. 사이클을 입력하는 데 필요한 k 단계의 수와 사이클의 길이를 결정하십시오.
• 1000000000000000000 번째 피보나치 수, 1,000,000,000은 1,000000000000000000 번째 피보나치 수가 ((1,000000000000000000 - k) % l) 번째 위치가 될주기를 결정하여 찾을 수 있습니다. 그러니 그 위치를보고 엔트리를 출력하십시오.