HDU - 4565So Easy!

知道这个套路才比较easy

\(a_n=(a+\sqrt{b})^n ,b_n=(a-\sqrt{b})^n\)且\(0<b_n<1\)
令\(c_n=a_n+b_n\)，所以
\(c_n=\lceil a_n \rceil\)

联系递推方程
\(F_n=pF_{n-1}+qF_{n-2}\)
\(a+\sqrt{b} ,a-\sqrt{b}\)是特征方程
\(x^2=px+q\)的两个根
算出p，q就可以像斐波那契数列一样用矩阵乘法

#include<cstdio>
#include<algorithm>
#include<cstring>
#include<map>
#include<queue>
#include<bitset>
#include<cmath>
#include<set>
#include<unordered_map>
#define fo(i,a,b) for (ll (i)=(a);(i)<=(b);(i)++)
#define fd(i,b,a) for (ll (i)=(b);(i)>=(a);(i)--)
#define mk(x,y) make_pair((x),(y))
//#define A puts("Yes")
//#define B puts("No")
using namespace std;
typedef double db;
typedef long long ll;
//typedef __int128 i128;
const int N=1e6+5;
const ll inf = 1ll << 60;
//const ll mo=1e9+7;
ll n,p,q,k,m,a,b;
struct mat{
	ll a[3][3];
	void init() {
		memset(a,0,sizeof(a));
	}
	friend mat operator * (const mat &a,const mat &b) {
		mat c;
		c.init();
		fo(i,1,2) fo(j,1,2) fo(k,1,2) { //
			c.a[i][j]+=a.a[i][k]*b.a[k][j]%m;
			c.a[i][j]%=m;			
		}
		return c;
	}
	void print(){
		fo(i,1,2) {
			fo(j,1,2) printf("%lld ",a[i][j]);
			printf("\n");
		}
	}
}; 

void solve(){
	mat t,y;
	t.init();
	y.init();
	if (n==1) {
		printf("%lld\n",2ll*a%m);
		return;
	}
	
	t.a[1][1]=(2ll*a%m*a%m+2ll*b%m)%m;
	t.a[2][1]=2ll*a%m;
	
	y.a[1][1]=2ll*a%m; y.a[1][2]=((b-a*a%m)%m+m)%m;
	y.a[2][1]=1;
	
	n-=2;
	while (n) {
		if (n&1) t=y*t;
		y=y*y;
		n/=2;
	}
	
	printf("%lld\n",t.a[1][1]);
}
int main()
{
//	freopen("data.in","r",stdin);
	
	while (scanf("%lld %lld %lld %lld",&a,&b,&n,&m)!=EOF) {
		solve();
	}
	
	return 0;
}

UVA 10655 Contemplation! Algebra
给出a+b,ab,n，求\(a^n+b^n\)
一样的套路，将a，b看作是特征方程的根，然后还原方程的系数。