261. Discrete Roots

求出的所有解。

找到一个特解

因为是质数，所以可以求出的质数。因此对于模意义下的任意数有且仅有一个数满足。

假设，则，稍加变换，有：

然后套用就一定能求出，然后得到原方程的一个特解

找到所有解

则，

对上面的式子，显然有，设，则有

code:

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn=(1<<16)-1;
int gcd(int a,int b) {
    if(!b) return a;
    while((a%=b) && (b%=a));
    return a+b;
}
int qpow(ll a,ll b,int mod) {
    ll res=1;
    while(b) {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int generator(int p) {
    vector<int> fact;
    int phi = p - 1, n = phi;
    for (int i = 2; i * i <= n; ++i) {
        if (n % i == 0) {
            fact.push_back(i);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) fact.push_back(n);
    for (int res = 2; res <= p; ++res) {
        bool ok = true;
        for (int factor : fact) {
            if (qpow(res, phi / factor, p) == 1) {
                ok = false;
                break;
            }
        }
        if (ok) return res;
    }
    return -1;
}
struct HASH{
    int v[maxn+1],tot,ed=0;
    struct node{
        int t,p,next;
    }a[maxn<<1];
    void ins(int x,int y) {
        int k=x&maxn;
        if(v[k]!=ed) {
            v[k]=ed;
            a[k].t=x,a[k].p=y,a[k].next=0;
        }
        else {
            for(;;k=a[k].next) {
                if(a[k].t==x) return a[k].p=y,void();
                if(!a[k].next) break;
            }
            a[k].next=++tot,a[tot].t=x,a[tot].p=y,a[tot].next=0;
        }
    }
    int find(int x) {
        int k=x&maxn;
        if(v[k]!=ed) return -1;
        for(;;k=a[k].next)
            if(a[k].t==x) return a[k].p;
            else if(!a[k].next) return -1;
    }
}mp;
int bsgs(int g,int b,int p,int k) {
    if(b==1) return 0;
    int m=ceil(sqrt(p));
    mp.tot=maxn;
    ll tmp=1,s=1,x=qpow(g,k%(p-1),p);
    for(int j=0; j<m; ++j)
        mp.ins(tmp*b%p,j),tmp=tmp*x%p;
    for(int i=1; i<=m; ++i) {
        s=s*tmp%p;
        if(~mp.find(s)) return i*m-mp.find(s);
    }
    return -1;
}
signed main() {
    cin.sync_with_stdio(false), cin.tie(nullptr),cout.tie(nullptr);
    int p,k,a;
    cin>>p>>k>>a; mp.ed=1;
    if(a==0) return cout<<"1\n0\n",0;
    int g=generator(p);
    int res=bsgs(g,a,p,k);
    if(res==-1) return cout<<"0\n",0;
    int delta=(p-1)/gcd(k,p-1),tmp=qpow(g,delta,p);
    vector<int>ans;
    ans.emplace_back(qpow(g,res,p));
    for(res+=delta;res<p-1;res+=delta) 
        ans.emplace_back(1LL*ans.back()*tmp%p);
    sort(ans.begin(), ans.end());
    cout<<ans.size()<<'\n';
    for(int i:ans) cout<<i<<' ';
    return 0;
}

用代替的code