【题目来源】：https://vjudge.net/problem/HDU-4565 【题意】 题意如面。 【思路】 这种题主要是精度：”┍ ┑”这种是取大于等于当前值的整数。
然后主要就是一个转换的问题： a+sqrt（b）————->x1+y1(sqrt(b)) (a*a+b)+2*a*sqrt(b)—–>x2+y2(sqrt(b)) 然后也就是： Cn=(a+sqrt(b))ⁿ+(a-sqrt(b))ⁿ=(xn+yn*sqrt(b))+(xn-yn*aqrt(b))=2*xn; 因为b的范围：(a-1) ^2< b < a^2 so： 0<(a-sqrt(b))ⁿ<1;——————————① 然后回到精度的问题上： ①式恰好填上了精度、 so： Cn=┍ (a+sqrt(b))ⁿ ┑=2xn； so：（推理） Cn=(a+sqrt(b))ⁿ+(a-sqrt(b))ⁿ; ((a+sqrt(b))+(a-sqrt(b)))*Cn=Cn+1+(a*a-b)Cn-1; 推出矩阵： 2*a b-a*a 1 0 ，对了，因为b
#include<cmath> #include<cstdio> #include<cstring> #include<algorithm> #define LL long long using namespace std; LL a,b,n,m; struct mat { LL a[3][3]; mat() { memset(a,0,sizeof(a)); } }; mat operator*(mat s,mat t) { mat r; for(int i=1; i<=2; i++) { for(int j=1; j<=2; j++) { for(int k=1; k<=2; k++) { r.a[i][j]+=s.a[i][k]*t.a[k][j]; if(r.a[i][j]>=m) r.a[i][j]%=m; } } } return r; } mat pow_mat(mat base,LL k) { mat ans; for(int i=1; i<=2; i++) ans.a[i][i]=1; while(k) { if(k&1) ans=ans*base; base=base*base; k>>=1; } return ans; } int main() { while(~scanf("%lld%lld%lld%lld",&a,&b,&n,&m)) { if(n==0) printf("%lld\n",2%m); else if(n==1) printf("%lld\n",2*a%m); else { mat base; base.a[1][1]=2*a%m; base.a[1][2]=(-a*a+b)%m; base.a[2][1]=1; base.a[2][2]=0; mat ans=pow_mat(base,n-1); LL sum=((ans.a[1][1]*2*a+ans.a[1][2]*2)%m+m)%m; printf("%lld\n",sum); } } }