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(n&1) 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