HDU - 4549 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]的值吗？

Input

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

Output

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

Sample Input

0 1 0
6 10 2

Sample Output

0
60

F(n)不是线性递推式，先推一下规律：

F(0)=a

F(1)=b

F(2)=a*b

F(3)=(a^1)*(b^2)

F(4)=(a^2)*(b^3)

F(5)=(a^3)*(b^5)

……

发现F(n)=(a^f(n-2))*(b^f(n-1))

其中f(n)为斐波那契序列，f(0)=1,f(1)=1,f(2)=2……

两个幂之积然后取模一个素数，由费马小定理：

(a^b)%p=a^(b%(p-1))

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2;
const int MOD=1e9+7;
struct mat
{
    ll a[N][N];
};
mat mat_mul(mat x,mat y)
{
    mat res;
    memset(res.a,0,sizeof(res.a));
    for(int i=0; i<2; i++)
        for(int j=0; j<2; j++)
            for(int k=0; k<2; k++)
                res.a[i][j]=(res.a[i][j]+x.a[i][k]*y.a[k][j])%(MOD-1);///费马小定理
    return res;
}

mat mat_pow(ll n)
{
    mat c,res;
    c.a[0][0]=c.a[0][1]=c.a[1][0]=1;
    c.a[1][1]=0;
    memset(res.a,0,sizeof(res.a));
    res.a[0][0]=res.a[1][1]=1;
    while(n)
    {
        if(n&1)
            res=mat_mul(res,c);
        c=mat_mul(c,c);
        n=n>>1;
    }
    return res;
}

ll quick(ll a,ll b)
{
    ll ans=1;
    a%=MOD;
    while(b)
    {
        if(b&1)
            ans=((ans%MOD)*(a%MOD))%MOD;
        a=((a%MOD)*(a%MOD))%MOD;
        b>>=1;
    }
    return ans;
}
int main()
{
    ll n,x,y;
    while(~scanf("%lld%lld%lld",&x,&y,&n))
    {
        if(x==0||y==0)
        {
            cout<<0<<'\n';
            continue;
        }
        if(n==0)
        {
            cout<<x%MOD<<'\n';
            continue;
        }
        if(n==1)
        {
            cout<<y%MOD<<'\n';
            continue;
        }
        mat res=mat_pow(n-2);
        ll tmp1=(res.a[0][0]%(MOD-1)+res.a[0][1]%(MOD-1))%(MOD-1);///两个指数取模（MOD-1）
        ll tmp2=(res.a[1][0]%(MOD-1)+res.a[1][1]%(MOD-1))%(MOD-1);
//        cout<<tmp1<<' '<<tmp2<<'\n';
        ll ans1=quick(x,tmp2%(MOD-1));
        ll ans2=quick(y,tmp1%(MOD-1));
        ll ans=((ans1%MOD)*(ans2%MOD))%MOD;///乘法取模（正常）
        cout<<ans<<'\n';
    }
    return 0;
}
//f(n)    1 1 f(1)
//f(n-1)  1 0 f(0)