BZOJ 1420: Discrete Root (原根+BSGS)

题意

已知$k$, $a$, $p$. 求 $x^kequiv a (mod p)$ 的所有根. 根的范围$[0,p-1]$. $p$为质数

分析

因为$p$是质数,那么一定有原根.设为$g$.
原根的性质如下:

• 对于$[1,p-1]$的所有$i$,一定存在$xin[1,p-1]$使得$g^xequiv i (mod p)$. 此时设$x$为$I(i)$.

$1.$那么当$a$等于$0$

• 只有一个根就是$0$

$2.$当$ain[1,p-1]$

• 画画柿子$egin{aligned}x^k&equiv a (mod p)\(g^{I(x)})^k&equiv a (mod p)\(g^{k})^{I(x)}&equiv a (mod p)end{aligned}$
  我们知道$g^k$,知道$a$,知道$p$.直接$BSGS$就行了.

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
int g, prime[100], cnt;
inline int qpow(int a, int b, int c) {
    int re = 1;
    while(b) {
        if(b&1) re = 1ll * re * a % c;
        a = 1ll * a * a % c; b >>= 1;
    }
    return re;
}
inline void Factor(int N) {
    int tmp = N;
    for(int i = 2; i*i <= N; ++i)
        if(tmp % i == 0) {
            prime[++cnt] = i;
            while(tmp % i == 0) tmp /= i;
        }
    if(tmp > 1) prime[++cnt] = tmp;
}
inline int Get_g(int p) { //找原根
    Factor(p-1);
    for(int g = 2; ; ++g) {
        bool flg = true;
        for(int i = 1; i <= cnt; ++i)
            if(qpow(g, (p-1)/prime[i], p) == 1)
                { flg = 0; break; }
        if(flg) return g;
    }
}
map<int, int>myhash;
vector<int>ans;
inline void Baby_Step_Giant_Step(int a, int b, int p) {
    if(b == 1) ans.push_back(0);
    myhash.clear();
    int m = int(sqrt(p) + 1);
    LL base = b;
    for(int i = 0; i < m; ++i) {
        myhash[base] = i;
        base = 1ll * base * a % p;
    }
    base = qpow(a, m, p);
    LL tmp = 1;
    for(int i = 1; i <= m+1; ++i) {
        tmp = 1ll * tmp * base % p;
        if(myhash.count(tmp))
            ans.push_back(i*m - myhash[tmp]);
    }
}
int main() {
    int p, k, a, g;
    scanf("%d%d%d", &p, &k, &a);
    if(!a) return puts("1"), puts("0"), 0;
    //(g^I(x))^k = a (mod p)
    //(g^k)^I(x) = a
    Baby_Step_Giant_Step(qpow(g = Get_g(p), k, p), a, p);
    for(int i = 0, siz = ans.size(); i < siz; ++i)
        ans[i] = qpow(g, ans[i], p);
    sort(ans.begin(), ans.end());
    int siz = ans.size();
    siz = unique(ans.begin(), ans.end()) - ans.begin();
    printf("%d
", siz);
    for(int i = 0; i < siz; ++i)
        printf("%d
", ans[i]);

}