本文主要是介绍HDU 4565 So Easy!，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
点击打开链接
本题题意：
给出整数a,b,n,m求出Sn。
l0<a, m < 2 15, (a-1) 2<b < a 2, 0 < b, n < 2 31
解题思路：
因为a，b，n很大所以如果直接求(a+sqrt(b))^n会爆double范围 所以只能对公式化简。由题中b的范围为(a-1) 2<b < a 2 知道(a-1)<sqrt(b)<a,所以我们可以得出0<a-sqrt(b)<1,即有共轭的性质可知(a+sqrt(b))^n+(a-sqrt(b))^n 为整数并等于(a+sqrt(b))^n向上取整所以设Sn＝[(a+sqrt(b))^n+(a-sqrt(b))^n]%m 我们可以两边同时乘以(a+sqrt(b))+(a-sqrt(b)) 可化简为Sn+1=(2*a)Sn-(a*a-b)Sn-1;所以我们在用矩阵快速幂就可以做了
代码：
#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
typedef long long ll;
const double eps=1e-6;
const int MAX = 2;
ll mod;
typedef struct
{ll m[MAX][MAX];
}Matrix;
Matrix P;//构造矩阵
Matrix I;//原始矩阵*/
Matrix matrixmul(Matrix a,Matrix b)
{int i,j,k;Matrix c;for (i = 0 ; i < MAX; i++)for (j = 0; j < MAX; j++){c.m[i][j] = 0;for (k = 0; k< MAX; k++)c.m[i][j]=(c.m[i][j] +(a.m[i][k] * b.m[k][j])%mod+mod)%mod;}return c;
}Matrix quickpow(long long n)
{Matrix m =P,b=I;while (n){if(n&1)b = matrixmul(b,m);n = n/2;m = matrixmul(m,m);}return b;
}
long long a,b,m,n;
ll s[3];
void init(){s[1]=(a+sqrt(b))+a-sqrt(b)+eps;s[2]=pow(a+sqrt(b),2)+pow(a-sqrt(b),2)+eps;// cout<<s[1]<<' '<<s[2]<<endl;mod=m;P={2*a,1ll,-(a*a-b),0};I={s[2],s[1],0,0};
}
int main(int argc, const char * argv[]) {while (cin>>a>>b>>n>>m) {init();if (n<=2) {cout<<(s[n])%m<<endl;}else {Matrix c=quickpow(n-2);// double ss=s[2]*c.m[0][0]+s[1]*c.m[1][0];cout<<c.m[0][0]%m<<endl;}}return 0;
}这篇关于HDU 4565 So Easy!的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
