NYOJ 1000 又见斐波那契数列

描述

斐波那契数列大家应该很熟悉了吧。下面给大家引入一种新的斐波那契数列：M斐波那契数列。 M斐波那契数列F[n]是一种整数数列，它的定义如下：

F[0] = a
F[1] = b
F[n] = F[n-1] * F[n-2] ( n > 1 )

现在给出a, b, n，聪明的你能求出F[n]的值吗？

输入

输入包含多组测试数据；
每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ）

输出

对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。

样例输入

0 1 0

6 10 2

样例输出

0

60

Solution:

　　本题我们容易发现$F[0]=a,F[1]=b,F[2]=ab,F[3]=ab^2,F[4]=a^2b^3,F[5]=a^3b^5…$，设$f[i]表示第i个斐波拉契数$，则$F[n]=a^{f[n-1]}b^{f[n]},n≥2$

　　于是，$F[n]=a^{f[n-1]}b^{f[n]}\;mod\;p$，关键是$ a,b $指数会很大，由扩展欧拉定理（关于扩展欧拉定理）:

$a^n≡a^{n\;mod\;\phi (p)}\;mod\;p,\quad gcd(a,p)=1$，注意到$ p $为素数，于是$gcd(a,p)=1,\phi (p)=p-1$，

那么本题就直接套上矩阵快速幂取对$p-1$取模求出$a,b$的系数，然后再普通快速幂对$p$取模求$ans$就$OK$了。

代码：

/*题意是给定F[1]=a，F[2]=b，F[n]=F[n-1]*F[n-2]，求第n项对素数m取模*/

#include<iostream>

#include<cstdio>

#include<cstring>

#define il inline

#define ll long long

#define mem(p) memset(&p,0,sizeof(p))

using namespace std;

const ll mod = 1e9+;

ll a,b,n,phi=mod-,mia,mib;

struct mat{ll a[][],r,c;};

il mat mul(mat x,mat y)

{

    mat p;

    mem(p);

    p.r=x.r,p.c=y.c;

    for(int i=;i<x.r;i++)

        for(int j=;j<y.c;j++)

            for(int k=;k<x.c;k++)

    p.a[i][j]=(p.a[i][j]+x.a[i][k]*y.a[k][j]%phi)%phi;

    return p;

}

il void fast(ll k)

{

    mat p,ans;

    mem(p),mem(ans);

    p.r=p.c=;

    p.a[][]=p.a[][]=p.a[][]=;

    ans.r=,ans.c=;

    ans.a[][]=,ans.a[][]=;

    while(k){

        if(k&)ans=mul(ans,p);

        p=mul(p,p);

        k>>=;

    }

    mib=ans.a[][];mia=ans.a[][];

}

il ll qpow(ll o,ll k)

{

    ll ans=;

    while(k)

    {

        if(k&)ans=ans*o%mod;

        k>>=;

        o=o*o%mod;

    }

    return ans;

}

int main()

{

    ios::sync_with_stdio();

    //cout<<phi<<endl;

    while(cin>>a>>b>>n){

        if(n==){cout<<(a>mod?a%mod:a)<<endl;continue;}

        if(n==){cout<<(b>mod?b%mod:b)<<endl;continue;}

        if(n==){cout<<a*b%mod<<endl;continue;}

            fast(n-);

        //    cout<<mia<<' '<<mib<<endl;

            cout<<qpow(a,mia)*qpow(b,mib)%mod<<endl;

    }

    return ;

}