题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=4565
矩阵快速幂，要推公式。
参考了网上的题解，简直屌
代码：
#include <stdio.h>
#include <string.h>
#include <math.h>
long long a, b, n, m;
struct mat {
long long v[2][2];
mat() {
memset(v, 0, sizeof(v));
}
mat operator * (mat a) {
mat c;
for (int i = 0; i < 2; i++)
for (int j = 0; j < 2; j++)
for (int k = 0; k < 2; k++) {
c.v[i][j] = ((c.v[i][j] + v[i][k] * a.v[k][j]) % m + m) % m;
}
return c;
}
};
mat pow_mod(mat a, long long k) {
if (k <= 1) return a;
mat ans = pow_mod(a * a, k / 2);
if (k&1) ans = ans * a;
return ans;
}
int main() {
while (~scanf("%lld%lld%lld%lld", &a, &b, &n, &m)) {
mat s;
s.v[0][0] = 2 * a; s.v[0][1] = -(a * a - b);
s.v[1][0] = 1; s.v[1][1] = 0;
long long c1 = (long long)(ceil(a + sqrt(b))) % m;
long long c2 = (long long)(ceil((a + sqrt(b)) * (a + sqrt(b)))) % m;
if (n == 1) printf("%lld\n", c1);
else if (n == 2) printf("%lld\n", c2);
else {
mat ans = pow_mod(s, n - 2);
printf("%lld\n", (((((ans.v[0][0] * c2 % m) + m) % m) + (((ans.v[0][1] * c1 % m) + m) % m)) + m) % m);
}
}
return 0;
}2013长沙邀请赛 HDU 4565 So Easy!(矩阵快速幂）,布布扣,bubuko.com
2013长沙邀请赛 HDU 4565 So Easy!(矩阵快速幂）
原文：http://blog.csdn.net/accelerator_/article/details/23514855