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);
    }
}

Posted by xiaodao
Category: 日常