http://www.lydsy.com/JudgeOnline/problem.php?id=2219
http://jcvb.is-programmer.com/posts/42036
考察同余方程…
a^x = b (mod p)
已知 x,b 时，求 a。
——
首先 CRT 。。。（保证 p 有原根可以取指标，取指标大概可以类比离散对数。。）
x ind a = ind b ( mod p)
求出原根 g。。(似乎只能暴力？
然后用 exDlog 求出 ind b。。。
于是就转换成了线性同余方程问题。。
https://gist.github.com/lychees/86926b622aac855acfb4
int getPrimitive(int p){
--p; VI d; for (int i=2;i*i<=p;++i) if (!(p%i)) d.PB(i), d.PB(p/i);
UNQ(d); MOD = ++p; FOR(i, 2, p){
int j = 0; REP_N(j, SZ(d)) if (pow(i, d[j]) == 1) break;
if (j == SZ(d)) return i;
}
assert(0);
return -1; //!
}
int f(int x, int b, PII p){
int pp = poww(p.fi, p.se); b %= pp; if (!b) return poww(p.fi, p.se - ceil(p.se, x));
int phi = pp-pp/p.fi, g=getPrimitive(p.fi);
MOD = pp; int bb = Dlog(g, b), d = gcd(x, phi);
return bb%d?0:d;
}
int main(){
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
//freopen("out.txt", "w", stdout);
#endif
sieve(); Rush{
int x, b, p; RD(x, b, p); p<<=1, ++p; fact(p);
int res = 1; ECH(it, fac) res *= f(x, b, *it);
OT(res);
}
}
