hdu-4549 M斐波那契数列 nyoj - 1000

本文主要是介绍hdu-4549 M斐波那契数列 nyoj - 1000，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

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

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

#include<stdio.h>
#include<string.h>
typedef __int64 LL;
#define MOD 1000000007
#define mod 1000000006
struct 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);}
}

这篇关于hdu-4549 M斐波那契数列 nyoj - 1000的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---