hdu 4565 So Easy!(矩阵快速幂）

题目链接：hdu 4565 So Easy!

题目大意：计算题目中所给式子的值。

解题思路：矩阵快速幂。

An = (a+√b)^n, Bn = (a-√b)^n, Cn = An + Bn = (a+√b)^n+(a-√b)^n;

因为说An和Bn共轭，展开式可以互相抵消，所以保证说Cn一定是整数。

(a-1)^2 < b < a^2

->a-1 < √b < a

-> 0 < a - √b < 1

-> 0 < (a - √b) < 1

-> [ Bn ] = 1

所以有Cn = [ An ]

Sn = Cn % m.

Sn * 2a = Sn * ((a + √b) + (a - √b)) =((a + √b)^n + (a - √b)^n)*((a + √b) + (a - √b))

= ((a + √b)^(n+1) + (a - √b)^(n+1)) + (a^2-b)((a + √b)^(n-1) + (a - √b)^(n-1))

= Sn+1 + (a^2-b)Sn-1

Sn+1 = 2aSn + (b-a^2)Sn-1.

#include <stdio.h>
#include <string.h>
#include <math.h>

#define MOD(a,b) (((a%b)+b)%b)
typedef long long ll;
const int N = 2;

int m;
struct mat {
	ll s[N][N];
	mat () {
		memset(s, 0, sizeof(s));
	}

	void set (ll a, ll b, ll c, ll d) {
		s[0][0] = a; s[0][1] = b;
		s[1][0] = c; s[1][1] = d;
	}

	mat operator * (const mat& c) {
		mat ans;
		for (int i = 0; i < N; i++) {
			for (int j = 0; j < N; j++) {
				
				for (int k = 0; k < N; k++)
					ans.s[i][j] = MOD(ans.s[i][j] + s[i][k] * c.s[k][j], m);
			}
		}
		return ans;
	}
}A;

mat powMat (int n) {

	mat ans;
	ans.set (1, 0, 0, 1);

	while (n) {
		if (n&1)
			ans = ans * A;
		n /= 2;
		A = A * A;
	}
	return ans;
}

int main () {
	int a, b, n;
	while (scanf("%d%d%d%d", &a, &b, &n, &m) == 4) {
		double t = pow (a + sqrt(b), 2);
		ll s1 = 2 * a % m;
		ll s2 = (ll)ceil(t) % m;

		if (n <= 1) {
			printf("%lld\n", s1);
		} else {
			A.set (2 * a, b - a * a, 1, 0);
			mat ans = powMat (n-2);

			printf("%lld\n", MOD(s2 * ans.s[0][0] + s1 * ans.s[0][1], m));
		}
	}
	return 0;
}