给一个素数p，整数k和a
就x^k=a(mod p)的所有整数解。。。
首先算出原根g
设x=g^i(mod p)
则首先若a==0(我就是忘处理这个所以WAN次囧。。)。。那么答案就是0.。
否则a=g^j(mod p)
那么g^(ik)=g^j
<=> ik=j(mod p-1)..
算出所有满足这个的i，代入得到所有x，排序就OK了。。
Code：
#include <vector>
#include <algorithm>
#include <utility>
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <set>
#include <map>
#include <cstring>
#include <time.h>
#define rep(i,n) for(int i=0;i<n;i++)
#define pb push_back
#define Debug(x) cout<<#x<<"="<<x<<endl;
#define tr(e,x) for(typeof(x.begin()) e=x.begin();e!=x.end();e++)
const int inf=~0U>>1,maxn=20;
using namespace std;
typedef long long ll;
ll P[maxn],m=0,p,g,k,a;
void decompose(ll x)
{
for(ll i=2;i*i<=x;i++)
if(x%i==0)
{
P[m++]=i;
while(x%i==0)x/=i;
}
if(x>1)P[m++]=x;
}
ll ext_gcd(ll a,ll b,ll&x,ll&y)
{
if(!b){x=1;y=0;return a;}
ll tmp=ext_gcd(b,a%b,y,x);y-=x*(a/b);
return tmp;
}
ll pow(ll x,ll e)
{
if(!e)return 1;
ll tmp=pow(x,e/2);tmp*=tmp;tmp%=p;
if(e&1)tmp*=x,tmp%=p;
return tmp;
}
ll inv(ll x)
{
return pow(x,p-2);
}
bool IsRoot(ll a)
{
rep(i,m)
if(pow(a,(p-1)/P[i])==1)return false;
return true;
}
void FindRoot()
{
decompose(p-1);
for(ll i=2;i<p;i++)if(IsRoot(i)){g=i;break;}
}
ll discrete_Log(ll a)
{
map<ll,ll> Map;ll M=sqrt(p)+1;
ll v=inv(pow(g,M));
ll e=1;Map[1]=0;
for(ll i=1;i<M;i++){e=e*g%p;if(!Map.count(e))Map[e]=i;}
for(ll i=0;i<M;i++)
{
if(Map.count(a))return i*M+Map[a];
a=a*v%p;
}
return -1;
}
vector<ll> Solve(ll a,ll b,ll m)
{
ll x,y,d;
d=ext_gcd(a,m,x,y);
vector<ll> A;
if(b%d)return A;
ll t=b/d;x%=m;if(x<0)x+=m;x=x*t%m;
rep(i,d)
{
A.pb(x);
x+=m/d;x%=m;
}
return A;
}
int main()
{
//freopen("in","r",stdin);
cin>>p>>k>>a;
if(a==0){cout<<1<<endl<<0<<endl;return 0;}
FindRoot();
ll Loga=discrete_Log(a);
vector<ll> Logx=Solve(k,Loga,p-1);
cout<<Logx.size()<<endl;
vector<ll> Ans;
tr(it,Logx)
{
ll tmp=pow(g,*it);
Ans.pb(tmp);
}
sort(Ans.begin(),Ans.end());
tr(it,Ans)cout<<*it<<endl;
}