WA40分/kk

#include<cmath>
#include<cstdio>
#include<cstring>
const int mod=1e6+7;
#define int long long
inline void read(int &sum) {
	sum=0;int f=1; char ch=getchar();
	while(ch<'0'||ch>'9') {if(ch=='-') f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){sum=(sum<<3)+(sum<<1)+(ch^'0');ch=getchar();}
	sum*=f;
}

int a,b,p,map[mod+110],idx[mod+110];

inline int find(int x){
	int t=x%mod;
	while(map[t]&&map[t]^x){t+=107;if(t>=mod)t-=mod;}
	return t;
}
inline void ins(int id,int x){int f=find(x);map[f]=x,idx[f]=id;}
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int BSGS(int a,int b,int p,int ex){
	int m=ceil(sqrt(p)),s=1;
	memset(map,0,sizeof map);
	for(int i=0;i<=m;++i,s=s*a%p,b=a*b%p)ins(i,b);a=s;
	for(int i=1,f,tmp=a*ex;i<=m;++i,a=s*a%p,tmp=a*ex){
		if(map[f=find(tmp)]==tmp)return i*m-idx[f];
	}
	return -1;
}
int exBSGS(int a,int b,int p){
	a%=p,b%=p;
	if(!b){
		int d,cnt=0;
		while((d=gcd(a,p))^1){
			++cnt;p/=d;
			if(p==1)return cnt;
		}
		return -1;
	}
	if(!a)return -1;
	if(b==1)return 0;
	int ex=1,d,cnt=0;
	while((d=gcd(a,p))^1){
		if(b%d)return -1;
		b/=d,p/=d;++cnt;
		ex=(ex*a/d)%p;
		if(ex==b)return cnt;
	}
	int ans=BSGS(a,b,p,ex);
	if(~ans)return ans+cnt;
	return -1;
}
signed main(){
	//freopen("std.in","r",stdin);freopen("my.out","w",stdout);
	while(1){
		read(a),read(p),read(b);
		if(!a&&!b&&!p)break;
		int ans=exBSGS(a,b,p);
		if(~ans)printf("%lld\n",ans);
		else puts("No Solution");
	}
	return 0;
}