BZOJ1420: Discrete Root && BZOJ1319

题解:

事实上$p$是质数...

所以我们先求出原根$g$.

然后对于两边取指标,就得到$ind(x)\times{k}\equiv{ind(a)}\pmod{p-1}$

这就可以直接用拓展欧几里得算法求解了.

至于拓展欧几里得的一些细节见代码吧...

代码:

#include<cmath>
#include<cstdio>
#include<cctype>
#include<vector>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long ll;
 
ll pow(ll x,ll y,ll p){
    ll re=1,t=x;
    for(;y;y>>=1,t=t*t%p)
        if(y&1)
            re=re*t%p;
    return re;
}
 
inline void exgcd(ll a,ll b,ll&d,ll&x,ll&y){
    if(!b){
        d=a;
        x=1;
        y=0;
    }
    else{
        exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
 
struct Hashset{
    static const int mod=1313131;
    int head[mod],next[30010],f[30010],v[30010],ind;
    inline void reset(){
        memset(head,-1,sizeof head);
        ind=0;
    }
    inline int operator[](int x){
        int ins=x%mod;
        for(int j=head[ins];j!=-1;j=next[j])
            if(f[j]==x)
                return v[j];
        return -1;
    }
    inline void insert(int x,int _v){
        int ins=x%mod;
        for(int j=head[ins];j!=-1;j=next[j])
            if(f[j]==x){
                v[j]=min(v[j],_v);
                return;
            }
        f[ind]=x;
        v[ind]=_v;
        next[ind]=head[ins];
        head[ins]=ind++;
    }
}M;
 
inline ll BSGS(ll a,ll b,ll p){
    ll m=ceil(sqrt(p)),i,j,t;
    M.reset();
    for(t=1,i=0;i<m;++i,(t*=a)%=p)
        M.insert(t,i);
    ll rev=pow(t,p-2,p);
    for(i=0;i*m<p;++i,(b*=rev)%=p)
        if(M[b]!=-1)
            return i*m+M[b];
    return -1;
}
 
inline ll get_g(ll p){
    static int pr[110];
    int num=0;
    ll t=p-1;
    for(int i=2;i*i<=p;++i){
        if(t%i==0){
            pr[++num]=i;
            while(t%i==0)
                t/=i;
        }
    }
    if(t!=1)
        pr[++num]=t;
    for(int i=1;;++i){
        bool ok=1;
        for(int j=1;j<=num;++j)
            if(pow(i,(p-1)/pr[j],p)==1){
                ok=0;
                break;
            }
        if(ok)
            return i;
    }
}
 
inline ll gcd(ll a,ll b){
    return(!b)?a:gcd(b,a%b);
}
 
#define pb push_back
vector<ll>ans;
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
    ll p,k,a,i,j;
    cin>>p>>k>>a;
    ll g=get_g(p);
    if(a==0)
        printf("1\n0");
    else{
        ll ind_a=BSGS(g,a,p);
        if(ind_a%gcd(k,p-1))
            puts("0");
        else{
            ll temp=(p-1)/gcd(k,p-1);
            ll d,x,y;
            exgcd(k,p-1,d,x,y);
            x=(x%temp+temp)%temp;
            ind_a/=gcd(k,p-1);
            (x*=ind_a)%=temp;
            while(x<p){
                ans.pb(pow(g,x,p));
                x+=temp;
            }
            sort(ans.begin(),ans.end());
            for(printf("%d\n",ans.size()),i=0;i<ans.size();++i)
                printf("%lld\n",ans[i]);
        }
    }
    return 0;
}