HDU 5667 构造矩阵快速幂

题目描述

解析

我们根据递推公式

设

则可得到Q的指数关系式

求Q构造矩阵

同时有公式

其中φ为欧拉函数,且当p为质数时有

代码

#include <cstdio>using namespace std;long long pow_mod(long long a, long long p, long long mod) {
if (p == 0) return 1;
long long ans = pow_mod(a, p / 2, mod);
ans = (ans * ans) % mod;
if (p % 2) ans = (ans * a) % mod;
return ans;
}long long get_p(long long c, long long n, long long mod) {
long long ans[3][3] = {{0, 0, 0}, {1, 0, 0}, {1, 0, 0}};
long long a[3][3] = {{0, 1, 0}, {1, c, 1}, {0, 0, 1}};
long long b[3][3];
while (n) {
if (n & 1) {
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
b[i][j] = 0;
for (int k = 0; k < 3; k++) {
b[i][j] += a[i][k] * ans[k][j];
b[i][j] %= mod;
}
}
}
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
ans[i][j] = b[i][j];
}
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
b[i][j] = 0;
for (int k = 0; k < 3; k++) {
b[i][j] += a[i][k] * a[k][j];
b[i][j] %= mod;
}
}
}
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
a[i][j] = b[i][j];
n >>= 1;
}
return ans[1][0];
}int T;
long long n, a, b, c, p;
long long phi;int main() {
scanf("%d", &T);
while (T--) {
scanf("%I64d %I64d %I64d %I64d %I64d", &n, &a, &b, &c, &p);
if (n <= 2) phi = n - 1;
else phi = get_p(c, n - 2, p - 1);
printf("%I64d\n", pow_mod(pow_mod(a, b, p), phi, p));
}
return 0;
}