[文章目录]
Description
已知k，a，p，求x ^ k=a (mod p)的所有根 根的范围[0,p-1] a,p<=e19 k<=1e5 p为质数
原根与指标+BSGS+扩展gcd
方程两边取对数，变为与指数有关的方程：
对于底数，我们需求一个底数，使得其在 mod p意义下的次幂可以遍历所有值。这样的底数称为p的原根。
【据PoPoQQQ的课件，10^9以内奇素数的原根最大值在n^0.25以内】，那么直接枚举原根是谁，之后检验即可。
那么我们有了一个原根，设为g。BSGS求出log(a) : g^log(a)=a(mod p)，设为c
设 为b,k为a那么方程转化为 a * log(x) +b * y =c
扩展gcd求出解集{ai}，g^ai即为原方程的解集。
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long ll;
int p,k,a,g,pri[40],cnt,fna[1001000],tot;
map<int,int>mp;
int Pow(ll x,int y,int mod)
{
ll re=1;
while(y)
{
if(y&1) re=re*x%mod;
x=x*x%mod; y>>=1;
}
return re;
}
ll extgcd(ll A,ll B,ll &x,ll &y)
{
if(B==0) {x=1; y=0; return A;}
ll re=extgcd(B,A%B,y,x); y=y-A/B*x;
return re;
}
int main()
{
scanf("%d%d%d",&p,&k,&a); a%=p; k%=(p-1);
int t=p-1;
for(int i=2;i*i<=t;++i) if(t%i==0)
{
pri[++cnt]=i;
while(t%i==0) t/=i;
}
if(t!=1) pri[++cnt]=t;
for(int i=1;i<=cnt;++i) pri[i]=(p-1)/pri[i];
int g=-1;
for(int i=1;i!=p;++i)
{
g=-1;
for(int j=1;j<=cnt;++j)
if(Pow(i,pri[j],p)==1) {g=0; break;}
if(g==-1) {g=i; break;}
}
int inda=0,m=(int)sqrt((double)p-1)+1;
ll gm=1;
for(int i=0;i<m;++i)
{
mp[gm*a%p]=i;
gm=gm*g%p;
}
ll ans=1;
for(int i=1;i<=m+1;++i)
{
ans=ans*gm%p;
if(mp.find(ans)!=mp.end())
{inda=i*m-mp[ans]; break;}
}
ll x,y,gcd,A=k,B=p-1;
gcd=extgcd(A,B,x,y);
if(inda%gcd==0)
{
inda/=gcd; A/=gcd; B/=gcd;
x=(x*inda%B+B)%B;
while(x<p)
{
fna[++tot]=Pow(g,x,p);
x+=B;
}
}
sort(fna+1,fna+tot+1);
printf("%d\n",tot);
for(int i=1;i<=tot;++i)
printf("%d\n",fna[i]);
return 0;
}