51Nod1038 X^A Mod P 数论 原根 BSGS

时间：2022-08-06 08:30:23

原文链接https://www.cnblogs.com/zhouzhendong/p/51Nod1038.html

题目传送门 - 51Nod1038

题意

51Nod1038 X^A Mod P 数论 原根 BSGS

题解

　　在模质数意义下，求高次剩余，模板题。

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;

}

　　

相关文章