原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1038.html
题目传送门 - 51Nod1038
题意
题解
在模质数意义下，求高次剩余，模板题。
UPD(2018-09-10):
详见数论总结。
传送门 - https://www.cnblogs.com/zhouzhendong/p/Number-theory-Residue-System.html
代码
优化了一下代码……原来的那个在这一份后面……
#include <bits/stdc++.h>
using namespace std;
const int N=100005;
int T,A,B,P;
int Fac_p[N],Fac_tot,g;
int prime[N],vis[N],pcnt=0;
void Get_prime(int n){
memset(vis,0,sizeof vis);
pcnt=0;
for (int i=2;i<=n;i++){
if (vis[i])
continue;
prime[++pcnt]=i;
for (int j=i+i;j<=n;j+=i)
vis[j]=1;
}
}
int Pow(int x,int y,int mod){
int ans=1;
for (;y;y>>=1,x=1LL*x*x%mod)
if (y&1)
ans=1LL*ans*x%mod;
return ans;
}
bool Get_g_Check(int P,int x){
for (int i=1;i<=Fac_tot;i++)
if (Pow(x,(P-1)/Fac_p[i],P)==1)
return 0;
return 1;
}
int Get_g(int P){
Fac_tot=0;
int v=P-1;
for (int i=1;prime[i]*prime[i]<=v&&i<=pcnt;i++)
if (v%prime[i]==0){
Fac_p[++Fac_tot]=prime[i];
while (v%prime[i]==0)
v/=prime[i];
}
if (v>1)
Fac_p[++Fac_tot]=v;
for (int i=2;;i++)
if (Get_g_Check(P,i))
return i;
return -1;
}
struct hash_map{
static const int Ti=233,mod=1<<16;
int cnt,k[mod+1],v[mod+1],nxt[mod+1],fst[mod+1];
int Hash(int x){
int v=x&(mod-1);
return v==0?mod:v;
}
void clear(){
cnt=0;
memset(fst,0,sizeof fst);
}
void update(int x,int a){
int y=Hash(x);
for (int p=fst[y];p;p=nxt[p])
if (k[p]==x){
v[p]=a;
return;
}
k[++cnt]=x,nxt[cnt]=fst[y],fst[y]=cnt,v[cnt]=a;
return;
}
int find(int x){
int y=Hash(x);
for (int p=fst[y];p;p=nxt[p])
if (k[p]==x)
return v[p];
return 0;
}
int &operator [] (int x){
int y=Hash(x);
for (int p=fst[y];p;p=nxt[p])
if (k[p]==x)
return v[p];
k[++cnt]=x,nxt[cnt]=fst[y],fst[y]=cnt;
return v[cnt]=0;
}
}Map;
int BSGS(int A,int B,int P){
// Solve x : A^x = B (mod p)
// ans = aM+b
int M=max((int)(sqrt(1.0*P)),1),AM=Pow(A,M,P),AI=Pow(A,P-2,P);
Map.clear();
for (int b=0,pw=B;b<M;b++,pw=1LL*pw*AI%P)
Map.update(pw,b+1);
for (int a=0,pw=1;a<P;a+=M,pw=1LL*pw*AM%P){
int v=Map.find(pw);
if (v)
return a+v-1;
}
return -1;
}
int exgcd(int a,int b,int &x,int &y){
if (!b){
x=1,y=0;
return a;
}
int res=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return res;
}
vector <int> ans;
void Get_ans(int a,int c,int p){
// ax = c (mod p)
// ax + py = c
int x,y,g=exgcd(a,p,x,y);
ans.clear();
if (c%g)
return;
a/=g,c/=g;
int P=p/g;
x=(1LL*x*c%P+P)%P;
while (x<p)
ans.push_back(x),x+=P;
}
int main(){
Get_prime(1e5);
scanf("%d",&T);
while (T--){
scanf("%d%d%d",&P,&A,&B);
g=Get_g(P);
int t=BSGS(g,B,P);
Get_ans(A,t,P-1);
if (ans.size()<1)
puts("No Solution");
else {
for (vector <int> :: iterator i=ans.begin();i!=ans.end();i++)
(*i)=Pow(g,*i,P);
sort(ans.begin(),ans.end());
for (vector <int> :: iterator i=ans.begin();i!=ans.end();i++)
printf("%d ",*i);
puts("");
}
}
return 0;
}
#include <bits/stdc++.h>
using namespace std;
const int N=105;
int T,A,B,P;
int Fac_p[N],Fac_tot,g;
int Pow(int x,int y,int mod){
int ans=1;
for (;y;y>>=1,x=1LL*x*x%mod)
if (y&1)
ans=1LL*ans*x%mod;
return ans;
}
bool Get_g_Check(int P,int x){
for (int i=1;i<=Fac_tot;i++)
if (Pow(x,(P-1)/Fac_p[i],P)==1)
return 0;
return 1;
}
int Get_g(int P){
Fac_tot=0;
int v=P-1;
for (int i=2;i*i<=v;i++)
if (v%i==0){
Fac_p[++Fac_tot]=i;
while (v%i==0)
v/=i;
}
if (v>1)
Fac_p[++Fac_tot]=v;
for (int i=2;;i++)
if (Get_g_Check(P,i))
return i;
return -1;
}
unordered_map <int,int> Map;
int BSGS(int A,int B,int P){
// Solve x : A^x = B (mod p)
// ans = aM+b
int M=(int)sqrt(1.0*P),AM=Pow(A,M,P),AI=Pow(A,P-2,P);
Map.clear();
for (int b=0,pw=B;b<M;b++,pw=1LL*pw*AI%P)
Map[pw]=b+1;
int Alim=(P+M-1)/M;
for (int a=0,pw=1;a<Alim;a++,pw=1LL*pw*AM%P)
if (Map[pw])
return a*M+Map[pw]-1;
return -1;
}
int exgcd(int a,int b,int &x,int &y){
if (!b){
x=1,y=0;
return a;
}
int res=exgcd(b,a%b,y,x);
y-=(a/b)*x;
return res;
}
vector <int> ans;
void Get_ans(int a,int c,int p){
// ax = c (mod p)
// ax + py = c
int x,y,g=exgcd(a,p,x,y);
ans.clear();
if (c%g)
return;
a/=g,c/=g;
int P=p/g;
x=(1LL*x*c%P+P)%P;
while (x<p)
ans.push_back(x),x+=P;
}
int main(){
scanf("%d",&T);
while (T--){
scanf("%d%d%d",&P,&A,&B);
g=Get_g(P);
int t=BSGS(g,B,P);
Get_ans(A,t,P-1);
if (ans.size()<1)
puts("No Solution");
else {
for (vector <int> :: iterator i=ans.begin();i!=ans.end();i++)
(*i)=Pow(g,*i,P);
sort(ans.begin(),ans.end());
for (vector <int> :: iterator i=ans.begin();i!=ans.end();i++)
printf("%d ",*i);
puts("");
}
}
return 0;
}