给定自然数 (a) 和正整数 (m)，求 (k<2cdot 10^{18}) 使得 (a^kequiv kpmod m)。(T) 组数据。
(Tle 100,a,mle 10^9)。
众所周知，(a^kmod m) 在不循环部分之后进入长度为 (varphi(m)) 的约数的循环。
于是我们解方程均只考虑 (ge mvarphi(m)) 的解，就不用考虑开头部分了。
考虑构造一个 (y)，使得存在 (x)，其中 (xequiv a^ypmod m)，(xequiv ypmod{varphi(m)})，可以得到 (a^xequiv a^yequiv xpmod m)。
需要 (a^yequiv ypmod{gcd(m,varphi(m))})，这是一个递归的子问题。用扩欧可以从 (y) 算出 (x)。
复杂度瓶颈在算 (varphi)，先筛出 (m) 的质因子再求，(O(frac{Tsqrt m}{log m}))。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N = 31625, M = 3403;
template<typename T>
void read(T &x){
int ch = getchar(); x = 0; bool f = false;
for(;ch < '0' || ch > '9';ch = getchar()) f |= ch == '-';
for(;ch >= '0' && ch <= '9';ch = getchar()) x = x * 10 + ch - '0';
if(f) x = -x;
} int ksm(int a, LL b, int mod){
int res = 1;
for(;b;b >>= 1, a = (LL)a * a % mod)
if(b & 1) res = (LL)res * a % mod;
return res;
}
int T, a, m, pri[M], tot, pr[15], cnt;
bool notp[N];
void init(int m){
notp[0] = notp[1] = true;
for(int i = 2;i <= m;++ i){
if(!notp[i]) pri[tot++] = i;
for(int j = 0;j < tot && i * pri[j] <= m;++ j){
notp[i * pri[j]] = true;
if(!(i % pri[j])) break;
}
}
} void fact(int x){ cnt = 0;
for(int i = 0;i < tot && pri[i] * pri[i] <= x;++ i) if(!(x % pri[i])){
x /= pri[i]; pr[cnt++] = pri[i]; while(!(x % pri[i])) x /= pri[i];
} if(x > 1) pr[cnt++] = x;
} int phi(int x){
int ans = x;
for(int i = 0;i < cnt && pr[i] * pr[i] <= x;++ i) if(!(x % pr[i])){
ans = ans / pr[i] * (pr[i] - 1); x /= pr[i];
while(!(x % pr[i])) x /= pr[i];
} if(x > 1) ans = ans / x * (x - 1);
return ans;
} int exgcd(int a, int b, int &x, int &y){
if(!b){x = 1; y = 0; return a;}
int d = exgcd(b, a % b, y, x);
y -= a / b * x; return d;
} LL calc(int a, int m){
if(m == 1) return 1;
int n = phi(m), x, y, d = exgcd(n, m, x, y);
LL u = calc(a, d), v = ksm(a, u, m);
LL ret = x * (v - u) / d % m, mod = (LL)m * n;
return (n * ret + u + mod) % mod + mod;
}
int main(){
read(T); init(N-1);
while(T --){
read(a); read(m); a %= m; fact(m);
printf("%lld
", calc(a, m));
}
}