题目链接：LightOJ 1070 Algebraic Problem
题意：已知a+b和ab的值求a^n+b^n。结果模2^64。
思路：
1.找递推式
得到递推式之后就是矩阵快速幂了
注意：模2^64，定义成unsigned long long 类型，因为无符号类型超过最大范围的数与该数%最大范围 的效果是一样的。
AC代码：
#include<stdio.h>#include<string.h>#define LL unsigned long longstruct Matrix {LL m[10][10];};LL n;Matrix geti(LL n) {LL i;Matrix b;memset(b.m,0,sizeof b.m);for(i=0;i<2;i++)b.m[i][i]=1;return b;}Matrix matrixmul(Matrix a,Matrix b) {LL i,j,k;Matrix c;for(i=0;i<2;i++) {for(j=0;j<2;j++) {c.m[i][j]=0.0;for(k=0;k<2;k++) {c.m[i][j]+=(a.m[i][k]*b.m[k][j]);}}}return c;}Matrix quickpow(Matrix a,LL p) {Matrix m=a;Matrix b=geti(n);while(p) {if(p%2)b=matrixmul(b,m);p/=2;m=matrixmul(m,m);}return b;}int main() {LL t;LL p,q;int cas=1;Matrix pp,init,ans;//printf("%llu\n",kmod);scanf("%llu",&t);while(t–) {scanf("%llu %llu %llu",&p,&q,&n);memset(pp.m,0,sizeof pp);pp.m[0][0]=p;pp.m[0][1]=1;pp.m[1][0]=-q;pp.m[1][1]=0;init.m[0][0]=p;init.m[0][1]=2;init.m[1][0]=0;init.m[1][1]=0;printf("Case %d: ",cas++);if(n==0){printf("%llu\n",init.m[0][1]);}else if(n==1){printf("%llu\n",init.m[0][0]);}else {ans=quickpow(pp,n-1);ans=matrixmul(init,ans);printf("%llu\n",ans.m[0][0]);}}return 0;}/* */
版权声明：本文为博主原创文章，，未经博主允许不得转载。
有事者，事竟成;破釜沉舟，百二秦关终归楚;苦心人，
