運用費馬小定理&&矩陣快速冪 ?求出 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);} }

與50位技術專家面對面20年技術見證，附贈技術全景圖

總結

以上是生活随笔為你收集整理的hdu-4549 M斐波那契数列 nyoj - 1000的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。