在O（logn）中查找第n个fib号

Question

我正在尝试解决此问题： SPOJ problem 。

[经过一番研究后，我发现归结为对第n个fib数的简单计算，但是n可以变得非常大，因此O（n）解决方案将无济于事。在Google上进行谷歌搜索，发现您可以在O（logn）中计算第n个fib数，并且也可以精确地执行此代码示例：

long long fibonacci(int n)
{
    long long fib[2][2]= {{1,1},{1,0}},ret[2][2]= {{1,0},{0,1}},tmp[2][2]= {{0,0},{0,0}};
    int i,j,k;
    while(n)
    {
        if(n&1)
        {
            memset(tmp,0,sizeof tmp);
            for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++)
                        tmp[i][j]=(tmp[i][j]+ret[i][k]*fib[k][j]);
            for(i=0; i<2; i++) for(j=0; j<2; j++) ret[i][j]=tmp[i][j];
        }
        memset(tmp,0,sizeof tmp);
        for(i=0; i<2; i++) for(j=0; j<2; j++) for(k=0; k<2; k++)
                    tmp[i][j]=(tmp[i][j]+fib[i][k]*fib[k][j]);
        for(i=0; i<2; i++) for(j=0; j<2; j++) fib[i][j]=tmp[i][j];
        n/=2;
    }
    return (ret[0][1]);
}

我尝试针对问题进行修改，但仍在获取WA：http://ideone.com/3TtE5m

我计算的模数运算错误吗？还是其他问题？

Answer 1

你的意思是我希望第n个斐波那契。

Answer 2

有一个非常简单的算法，仅使用整数：

Answer 3

[斐波那契数是连续分数对的连续收敛的比率，并且由任何连续分数的连续收敛的矩阵形成的行列式为+1或−1。