如何找到第n个Fibonacci数的二进制表示(How to find binary representation for n'th Fibonacci number)

 这是我在这里的第一篇文章，所以如果我犯了一些错误，请告诉我。 
 
 我得到了一个赋值，其中一部分需要第n个Fibonacci数的二进制表示。 Constraints- 
 
 
 
 ）C ++必须用作prog。 语言。 
 
 
 ）n'th fib。 数字必须以lg（n）时间计算。 
 
 
 我有一个函数，但它适用于整数。 但我必须计算的最大值约为10 ^ 6。 所以，我被困在这里。 无论我知道什么，我都无法在这种情况下应用，因为我可以产生第n个纤维。 使用字符串，但会有线性时间复杂度。 以下是该功能， 
 
void multiply(long int F[2][2], long int M[2][2]);
void power(long int F[2][2], long int n);

// Function to Calculate n'th fibonacci in log(n) time
long int fib(long int n)
{
    long int F[2][2] = {{1,1},{1,0}};
    if(n == 0)
        return 0;
    power(F, n-1);
    return F[0][0];
}

void power(long int F[2][2], long int n)
{
    if( n == 0 || n == 1)
        return;
    long int M[2][2] = {{1,1},{1,0}};

    power(F, n/2);
    multiply(F, F);

    if( n%2 != 0 )
        multiply(F, M);
}

void multiply(long int F[2][2], long int M[2][2])
{
    long int x =  (F[0][0]*M[0][0])%mod + (F[0][1]*M[1][0])%mod;
    long int y =  (F[0][0]*M[0][1])%mod + (F[0][1]*M[1][1])%mod;
    long int z =  (F[1][0]*M[0][0])%mod + (F[1][1]*M[1][0])%mod;
    long int w =  (F[1][0]*M[0][1])%mod + (F[1][1]*M[1][1])%mod;  
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

int main(){
    int n; cin >> n; cout << fib(n)<<endl; getchar();
}
 
 可以看出，此功能中只能使用预定义的数据类型。 

Its my first post here, so if I commit some mistake please let me know.
 
I have been given a assignment, and a part of it requires the binary representation of n'th Fibonacci number. Constraints- 
 
 
 
) C++ has to be used as prog. language.
 
 
) n'th fib. number has to be calculated in lg(n) time.
 
 
I have a function but it works on integers. But the maximum value for which I have to do calculations is about 10^6. So, I am badly stuck here. Whatever I know, I can't apply in this scenario, because I can generate n'th fib. using strings but that will have linear time complexity. following is the function, 
 
void multiply(long int F[2][2], long int M[2][2]);
void power(long int F[2][2], long int n);

// Function to Calculate n'th fibonacci in log(n) time
long int fib(long int n)
{
    long int F[2][2] = {{1,1},{1,0}};
    if(n == 0)
        return 0;
    power(F, n-1);
    return F[0][0];
}

void power(long int F[2][2], long int n)
{
    if( n == 0 || n == 1)
        return;
    long int M[2][2] = {{1,1},{1,0}};

    power(F, n/2);
    multiply(F, F);

    if( n%2 != 0 )
        multiply(F, M);
}

void multiply(long int F[2][2], long int M[2][2])
{
    long int x =  (F[0][0]*M[0][0])%mod + (F[0][1]*M[1][0])%mod;
    long int y =  (F[0][0]*M[0][1])%mod + (F[0][1]*M[1][1])%mod;
    long int z =  (F[1][0]*M[0][0])%mod + (F[1][1]*M[1][0])%mod;
    long int w =  (F[1][0]*M[0][1])%mod + (F[1][1]*M[1][1])%mod;  
    F[0][0] = x;
    F[0][1] = y;
    F[1][0] = z;
    F[1][1] = w;
}

int main(){
    int n; cin >> n; cout << fib(n)<<endl; getchar();
}
 
As it can be seen, only predefined data types can be used in this function. 

原文：https://stackoverflow.com/questions/9859115