You can not select more than 25 topics Topics must start with a letter or number, can include dashes ('-') and can be up to 35 characters long.

63 lines
1.4 KiB

2 years ago
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl "\n"
// 求单个数字的欧拉函数
int phi(int x) {
int res = x;
for (int i = 2; i <= x / i; i++)
if (x % i == 0) {
res = res / i * (i - 1);
while (x % i == 0) x /= i;
}
if (x > 1) res = res / x * (x - 1);
return res;
}
// 快速幂
int qmi(int a, int b, int p) {
int res = 1;
a %= p;
while (b) {
if (b & 1) res = res * a % p;
b >>= 1;
a = a * a % p;
}
return res;
}
int check(int a, int b, int c) {
int res = 1;
while (b--) {
res *= a;
if (res >= c) return res;
}
return res;
}
// 递归求解f(n)%m
int dfs(int n, int m) {
if (n == 0) return 1; // 递归出口
int p = phi(m); // 每一层递归都要求出phi(m)
int x = dfs(n / 10, p); // 下一层依赖项
int y = check(n % 10, x, m);
if (y >= m) { // 符合欧拉定理要求
int res = qmi(n % 10, x + p, m); // 开始套公式计算
if (res == 0) res += m; // 快速幂等于0说明是m的整数倍此时保留m
return res;
} else
return y; // 不比m大就是原来的y值
}
signed main() {
int T;
cin >> T;
while (T--) {
int a, c;
cin >> a >> c;
cout << dfs(a, c) % c << endl;
}
}