本文共 1218 字，大约阅读时间需要 4 分钟。

运用费马小定理&&矩阵快速幂  求出 a , b 的个数

运用快速幂求解 a^num1 * b ^ num2 % MOD

#include
   
    #include
    
     typedef __int64 LL;#define MOD 1000000007#define mod 1000000006struct matrix//矩阵{    LL Matrix[2][2];};matrix s ={    1,1,    1,0,};matrix m ={    1,0,    0,1,};matrix matrix_multiplication(matrix a,matrix b)//矩阵乘法{    matrix c;    for(int i = 0;i < 2;i ++)    {        for(int j =0;j < 2;j++)        {            c.Matrix[i][j] = 0;            for(int k = 0;k < 2;k++)                c.Matrix[i][j] = (c.Matrix[i][j] + a.Matrix[i][k]*b.Matrix[k][j]) % mod;        }    }    return c;}matrix Fast_power1(LL n)//矩阵快速幂{    matrix ret = m,p = s;    while(n)    {        if(n&1) ret = matrix_multiplication(ret,p);        p = matrix_multiplication(p,p);        n >>= 1;    }    return ret;}LL Fast_power2(LL x,LL num)//x^num%MOD的快速幂{    LL res = 1;    while(num)    {        if(num&1) res = (res * x) % MOD;        x = (x*x)%MOD;        num>>=1;    }    return res;}int main(){    LL a,b,n,x,y;    while(~scanf("%I64d%I64d%I64d",&a,&b,&n))    {        matrix k;        k = Fast_power1(n);        LL x = k.Matrix[1][1],y = k.Matrix[1][0];        LL z = (Fast_power2(a,x) * Fast_power2(b,y))%MOD;        printf("%I64d\n",z);    }}
    
   

转载地址：http://vfsgi.baihongyu.com/