51nod1242 斐波那契数列的第N项

2017年07月03日 10点热度 0人点赞 0条评论
基准时间限制:1 秒 空间限制:131072 KB 分值: 0 难度:基础题

51nod1242 斐波那契数列的第N项 收藏

51nod1242 斐波那契数列的第N项 关注
斐波那契数列的定义如下:
F(0) = 0
F(1) = 1
F(n) = F(n - 1) + F(n - 2) (n >= 2)
(1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, ...)
给出n,求F(n),由于结果很大,输出F(n) % 1000000009的结果即可。
Input
输入1个数n(1 <= n <= 10^18)。
Output
输出F(n) % 1000000009的结果。
Input示例
11
Output示例

89

#include
#include
#include
using namespace std;
long long  ans[2][2],n;
void fun()
{
    long long a[2][2]= {1,1,1,0},t[2][2]= {1,1,1,0};
    ans[0][0]=ans[1][1]=1;
    ans[0][1]=ans[1][0]=0;
    while(n)
    {
        if(n&1)
        {
            memcpy(t,ans,sizeof(t));
            memset(ans,0,sizeof(ans));
            for(int i=0; i<2; i++)
                for(int j=0; j<2; j++)
                {
                    for(int k=0; k<2; k++)
                        ans[i][j]+=t[i][k]*a[k][j];
                    ans[i][j]%=1000000009;
                }
        }
        memcpy(t,a,sizeof(t));
        memset(a,0,sizeof(a));
        for(int i=0; i<2; i++)
            for(int j=0; j<2; j++)
            {
                for(int k=0; k<2; k++)
                    a[i][j]+=t[i][k]*t[k][j];
                a[i][j]%=1000000009;
            }
        n>>=1;
    }
}
int main()
{
    while(~scanf("%lld",&n)&&n>=0)
    {
        n--;
        if(n>0)
        {
            fun();
            printf("%lldn",ans[0][0]);
        }
        else
            printf("0n");
    }
    return 0;
}

#include
#include
using namespace std;
const long long M= 1000000009;
long long f1,f2;
long long n;
int main()
{
    f1=1,f2=0;
    long long a=1,b=1,c=1,d=0;
    long long a1,b1,c1,d1;
    cin>>n;
    if(n==0)
    {
        cout<<0<>=1;
    }
    cout<
未经允许不得转载!51nod1242 斐波那契数列的第N项

update

纸上得来终觉浅, 绝知此事须躬行。