BSGS&ex_BSGS code-526互联

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,b,mod;
map<int,int> mp;
int ksm(int x,int y,int mod){
	int ans=1;
	while(y){
		if(y&1) ans=ans*x%mod;
		x=x*x%mod,y>>=1;
	}
	return ans;
}
void exgcd(int a,int b,int &x,int &y){
	if(b==0){
		x=1,y=0;
		return ;
	}
	exgcd(b,a%b,x,y);
	int xx=x,yy=y;
	x=yy,y=xx-a/b*yy;
}
int gcd(int a,int b){
	if(b==0) return a;
	return gcd(b,a%b);
}
int inv(int a,int mod){
	int x=0,y=0;
	exgcd(a,mod,x,y);
	return (x+mod)%mod;
}
int BSGS(int a,int b,int mod){
	int B=sqrt(mod)+2,iv=inv(a,mod),ans=1e10;
	mp.clear();
	for(int i=0,num=b;i<B;i++,num=num*iv%mod){
		if(mp.find(num)==mp.end()) mp[num]=i;
	}
	int T=ksm(a,B,mod);
	for(int i=0,num=1;i<=B;i++,num=num*T%mod){
		if(mp.find(num)!=mp.end()) ans=min(ans,i*B+mp[num]);
	}
	return ans;
}
int solve(int a,int b,int mod){
	if(mod==1) return 0;
	if(b==1) return 0;
	if(!a) return (!b)?1:-1;
	if(a==b) return 1;
	int d=gcd(a,mod);
	if(d==1) return BSGS(a,b,mod);
	if(b%d) return -1e9;
	mod/=d;
	return solve(a,b/d*inv(a/d,mod)%mod,mod)+1;
}
signed main(){
	freopen("data.in","r",stdin);
	while(1){
		scanf("%lld%lld%lld",&a,&mod,&b);
		if(!a) return 0;
		a%=mod,b%=mod;
		int ans=solve(a,b,mod);
		if(ans<0||ans>mod) printf("No Solution\n");
		else printf("%lld\n",ans);
	}
	return 0;
}