ExBSGS WA 40 求调
查看原帖
ExBSGS WA 40 求调
571147
zhlzt楼主2025/8/1 15:13

答案输出有解,我输出了 No Solution

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
unordered_map<int,int>vis;
void exgcd(int a,int b,ll &x,ll &y){
	if(!b){x=1,y=0;return;}
	exgcd(b,a%b,y,x); y-=(a/b)*x;
}
inline int qkpow(int a,int b,int p){
	int res=1;
	while(b){
		if(b&1) res=1ll*res*a%p;
		a=1ll*a*a%p; b>>=1;
	}
	return res;
}
int sol(int p,int b,int n){
	if(n==1 or p==1){
		return 0;
	}
	int m=ceil(sqrt(p)),tmp;
	vis.clear();
	for(int v=1;v<=m;v++){
		vis[1ll*n*qkpow(b,v,p)%p]=v;
	}
	for(int u=1;u<=m;u++){
		tmp=qkpow(b,u*m,p);
		if(vis.count(tmp)){
			return (u*m-vis[tmp]);
		}
	}
	return -1;
}
int main(){
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	int a,p,b;
	while(cin>>a>>p>>b){
		if(!a) return 0;
		a%=p,b%=p;
		int tmp,val=1,tag=1,cnt=0,res=-1;
		if(b==1 or p==1){
			cout<<0<<"\n";
			return 0;
		}
		while((tmp=__gcd(a,p))>1){
			if(b%tmp){tag=0;break;}
			b/=tmp,p/=tmp,cnt++;
			val=1ll*val*(a/tmp)%p;
			if(val==b){res=cnt;break;}
		}
		if(res>=0){
			cout<<res<<"\n";
			continue;
		}
		if(!tag){
			cout<<"No Solution\n";
			continue;
		}
		ll inv,num;
		exgcd(val,p,inv,num);
		b=1ll*b*inv%p;
		tmp=sol(p,a,b);
		if(tmp>=0) cout<<(tmp+cnt)<<"\n";
		else cout<<"No Solution\n";
	}
	return 0;
}
2025/8/1 15:13
加载中...