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;

}