设(a+sqrt(b))^n为(Xn + Yn*sqrt(b))，那么显然有(a+sqrt(b))^(n+1) 为 (a*Xn + b*Yn + (aYn+Xn)*sqrt(b))。
那么显然有(a+sqrt(b))的Xn，Yn可以表示为 :
然后又会发现，(a-sqrt(b))^n可以表示为：
那么会发现(a+sqrt(b))^n =(a+sqrt(b))^n +(a-sqrt(b))^n -(a-sqrt(b))^n = Xn+Yn*sqrt(b) +Xn-Yn*sqrt(b) -(a-sqrt(b))^n = 2*Xn – (a-sqrt(b))^n。
又由题意得a-sqrt(b)∈(0,1)，，切最终答案向上取整，所以可得最终答案为2×Xn。
去年长沙网赛的题，这种题都不能1Y还怎么玩？
#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 0x3f3f3f3fusing 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;A.Init(2,1,0);B.Init(2,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;}
风不懂云的漂泊，天不懂雨的落魄，眼不懂泪的懦弱，
