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;
}
转载于:https://www.cnblogs.com/ScratchingBear/p/5400498.html
