BZOJ 2219: 數論之神


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