63 lines
1.4 KiB
C++
63 lines
1.4 KiB
C++
#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;
|
||
}
|
||
} |