原根
- 只有 $ 2,4,,p^k,2p^k $(p为奇素数)
- $ O(n+\sqrt {\phi (n)}+n^{\frac{1}{4}}log^2n)$
cpp
int phi[N],root[N];
vector<int> prime,fac,ans;// 质数,欧拉函数的质因子,所有原根
void init(){
phi[1]=1;
for(int i=2;i<N;i++){
if(!phi[i]){
prime.push_back(i);
phi[i]=i-1;
}
for(int j=0;j<prime.size()&&prime[j]*i<N;j++){
if(i%prime[j]==0){
phi[i*prime[j]]=phi[i]*prime[j];
break;
}
else{
phi[i*prime[j]]=phi[i]*(prime[j]-1);
}
}
}
root[2]=1;
root[4]=3;
for(int i=1;i<prime.size();i++){
for(int j=1;j*prime[i]<N;j*=prime[i])root[j*prime[i]]=1;
for(int j=2;j*prime[i]<N;j*=prime[i])root[j*prime[i]]=1;
}
}
int qpow(int a,int b,int mod){
int ans=1;
for(;b;b>>=1){
if(b&1)ans=ans*a%mod;
a=a*a%mod;
}
return ans;
}
// sqrt(n)+n^{1/4}*log^2n
int findroot(int m){
if(m==2)return 1;
if(m==167772161)return 3;
if(m==469762049)return 3;
if(m==754974721)return 11;
if(m==998244353)return 3;
if(m==4)return 3;
int d=phi[m];
if(d%2==0){
fac.push_back(2);
while(d%2==0)d/=2;
}
for(int i=3;i*i<=d;i++){
if(d%i==0){
fac.push_back(i);
while(d%i==0)d/=i;
}
}
if(d>1)fac.push_back(d);
for(int g=2;;g++){
if(qpow(g,phi[m],m)!=1)continue;
bool ok=true;
for(auto &p:fac){
if(qpow(g,phi[m]/p,m)==1){
ok=false;
break;
}
}
if(ok)return g;
}
}
void getroot(int m,int x){
int res=1;
for(int i=1;i<=phi[m];i++){
res=res*x%m;
if(__gcd(i,phi[m])==1)ans.push_back(res);
}
}
void solve(){
int n,d;
cin>>n>>d;
if(!root[n]){
cout<<"0\n\n";
return;
}
fac.clear();
ans.clear();
getroot(n,findroot(n));
sort(ans.begin(),ans.end());
cout<<ans.size()<<"\n";
for(int i=1;i*d<=ans.size();i++)cout<<ans[i*d-1]<<" ";
cout<<"\n";
}