nyoj1000_快速幂_费马小定理

又见斐波那契数列

时间限制： 1000 ms | 内存限制：65535 KB

难度： 4

斐波那契数列大家应该很熟悉了吧。下面给大家引入一种新的斐波那契数列：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]的值吗？

</dd> </dl>

<dl class="others"> <dt> 输入 </dt> <dd> 输入包含多组测试数据；
每组数据占一行，包含3个整数a, b, n（ 0 <= a, b, n <= 10^9 ） </dd> <dt> 输出 </dt> <dd> 对每组测试数据请输出一个整数F[n]，由于F[n]可能很大，你只需输出F[n]对1000000007取模后的值即可，每组数据输出一行。 </dd> <dt> 样例输入 </dt> <dd>

0 1 0 
6 10 2

</dd> <dt> 样例输出 </dt> <dd>

0 
60

</dd> <dt> 上传者 </dt> <dd> TC_李远航 </dd> <dd> 解题思路：这个题需要用到费马小定理，要先知道什么叫做费马小定理。 </dd> <dd> 　　实际上就是这么一个式子 a^(p-1)≡1 (mod p)，意思是在取模的情况下这两边是相等的（p是质数时）。 </dd> <dd> 当p为质数时可以这么用，(a^b) %p=a^(b%(p-1))。 </dd> <dd> 但为什么这么用呢？ </dd> <dd> 　　 </dd> <dd> 　　

</dd> <dd> 　　b是一个质数的时候，可以分解成k(p-1)+c （c是b%（p-1）的余数）。 </dd> <dd> 　　。。。 </dd> <dd> 　另外本题先通过找规律得到这个： </dd> <dd>

　　　　　　　　　f(0)=a (1,0)

f(1)=b; (0,1)

f(2)=ab (1,1)

f(3)=abb (1,2)

f(4)=abbab (2,3)

f(5)=abbababb (3,5)

f(6)=abbababbabbab (5,8)

所以F(n)= [a^f(n-1) * b^f(n)] %mod = a^[f(n-1)%mod-1] * b^[f(n)%mod-1] %mod;

f(n)是一个标准的斐波那契数列，用矩阵快速幂求出来之后然后分别通过快速幂求a的幂，b的幂，然后可得出结果。

</dd> </dl>

#include <iostream>
#include <cstdio>
#include <cstring>
#define MOD 1000000006
#define MOD2 1000000007
using namespace std;


struct matrix{
    long long int m[2][2];
};

matrix base,ans;

void init(){//只初始化base和ans(单位矩阵)
    memset(base.m,0,sizeof(base.m));
    memset(ans.m,0,sizeof(ans.m));
    for(int i=0;i<2;i++){
        ans.m[i][i]=1;
    }

    base.m[0][0]=base.m[0][1]=base.m[1][0]=1;
}

matrix multi(matrix a,matrix b){
    matrix t;
    for(int i=0;i<2;i++){
        for(int j=0;j<2;j++){
            t.m[i][j]=0;
            for(int k=0;k<2;k++){
                t.m[i][j]=(t.m[i][j]+(a.m[i][k]%MOD)*(b.m[k][j]))%MOD;
            }
        }
    }
    return t;
}

long int fast_matrix(int n){
    while(n){
        if(n&1){
            ans=multi(ans,base);
        }
        base=multi(base,base);
        n>>=1;
    }
    return ans.m[1][0];
}

long long int fast_power(long long int a,long long int n){
    long long int ans=1,p=a;
    while(n){
        if(n&1){
            ans=((ans%MOD2)*(p%MOD2))%MOD2;
        }
        n>>=1;
        p=((p%MOD2)*(p%MOD2))%MOD2;
    }
    return ans;
}

int main()
{
    long long int a,b,n;
    while(~scanf("%lld %lld %lld",&a,&b,&n)){
        if(n==0){
            printf("%lld\n",a%MOD2);
            continue;
        }
        if(n==1){
            printf("%lld\n",b%MOD2);
            continue;
        }
        if(n==2){
            printf("%lld\n",a*b%MOD2);
            continue;
        }

            init();
            long long int f=fast_matrix(n);//fib(n)
            long long int f2=ans.m[1][1];//fib(n-1)

            long long int m1=fast_power(a,f2);
            long long int m2=fast_power(b,f);

            long long int ans=m1*m2%MOD2;
            printf("%lld\n",ans);





    }
    return 0;
}