# HDU 4565 So Easy! Matrix rapid power

Posted on Nov. 19, 2023, 10:36 p.m. by Timothy Jones

Set (a + SQRT (b)) ^ n for (Xn + Ynsqrt (b)), so there are clearly (a + SQRT (b)) ^ (n + 1) to (aXn Yn + + b * * SQRT (aYn + Xn) (b)).

Then obviously there is Xn of (a+ SQRT (b)), Yn can be expressed as:

â€‹

And then again, (a- SQRT (b))^n can be expressed as:

â€‹

You will find (a + SQRT (b)) ^ n = (a + SQRT (b)) ^ n + (a - SQRT (b)) ^ n - (a - SQRT (b)) ^ n = Xn + Ynsqrt (b) + Xn - Ynsqrt (b) - (a - SQRT (b)) ^ n = 2 * Xn - (a - SQRT (b)) ^ n.

A-sqrt (b)âˆˆ(0,1), so the final answer is 2Ã—Xn.

Last year changsha net match, this kind of problem can not 1Y return how to play?

``#include algorithm #include iostream #include cstring #include cstdlib #include cstdio #include queue #include cmath #include stack #include map #pragma comment(linker, "/STACK:1024000000") #define EPS (1e-8) #define LL long long #define ULL unsigned long long #define INF 0x3f3f3f3f using  namespace std; const int MAXN = 61; struct MAT { int row,col; int mat[MAXN][MAXN]; void Init(int R,int C,int val) { row = R,col = C; for(int i = 1; i = row; ++i) for(int j = 1; j = col; ++j) mat[i][j] = (i == j ? val : 0); } MAT Multi(MAT c,int MOD) { MAT tmp; tmp.Init(this-row,c.col,0); int i,j,k; for(k = 1; k = this-col; ++k) for(i = 1; i = tmp.row; ++i) for(j = 1; j = tmp.col; ++j) (tmp.mat[i][j] += (this-mat[i][k]*c.mat[k][j])%MOD) %= MOD; return tmp; } MAT Quick(int n,int MOD) { MAT res,tmp = *this; res.Init(row,col,1); while(n) { if(n1) res = res.Multi(tmp,MOD); tmp = tmp.Multi(tmp,MOD); n = 1; } return res; } void Output() { cout" **************** "endl; int i,j; for(i = 1; i = row; ++i) { for(j = 1; j = col; ++j) printf("%3d ",mat[i][j]); puts(""); } cout"  "endl; }}; int main() { int a,b,n,m; MAT A,B; freopen("data1.in","r",stdin); while(scanf("%d %d %d %d",a,b,n,m) ! = EOF) { a %= m,b %= m; Anderson, nit (2, 0); B.I nit (2, 0). B.mat[1][1] = a; B.mat[1][2] = b; B.mat[2][1] = 1; B.mat[2][2] = a; A.mat[1][1] = a; A.mat[2][1] = 1; B = B.Quick(n-1,m); B = B.Multi(A,m); printf("%d\n",(2*B.mat[1][1])%m); } return 0; }Copy the code``
Search