如果a和p互质，用扩欧求逆元就可以直接套用普通BSGS。考虑怎么将其化至这种情况。
注意到当x>=logp时gcd(ax,p)是一个定值，因为这样的话每个存在于a中的质因子，其在ax中的出现次数一定比在p中的多。
于是对x<logp的情况暴力验证。对x>=logp的情况，设d=gcd(ax,p)，剩下的问题变为求ax/d≡b/d(mod p/d)，这里ax和p/d显然就是互质的了。
要求解这个方程，显然不能把d直接乘过去（好像也说不清为啥）。首先b%d>0时无解。然后考虑从ax中分离一部分，使该部分能整除d，再将该部分除以d后移到式子右边。直接分离的话会爆long long，每次分离一个a即可。剩下的就是普通BSGS了。
#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<map>
using namespace std;
#define ll long long
int gcd(int n,int m){return m==?n:gcd(m,n%m);}
int read()
{
int x=,f=;char c=getchar();
while (c<''||c>'') {if (c=='-') f=-;c=getchar();}
while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();
return x*f;
}
int a,p,b;
map<int,int> f;
void exgcd(int a,int b,int &x,int &y)
{
if (b==)
{
x=,y=;
return;
}
exgcd(b,a%b,x,y);
int t=x;x=y;y=t-a/b*x;
}
int inv(int a)
{
int x,y;exgcd(a,p,x,y);
x=(x%p+p)%p;
return x;
}
int BSGS(int a,int b,int p)
{
int block=sqrt(p),t=;//cout<<a<<' '<<b<<' '<<p<<endl;
f.clear();
for (int i=;i<block;i++)
{
if (f.find(t)==f.end()) f[t]=i;
if (t==b) return i;
t=1ll*t*a%p;
}
int v=t;
for (int i=;i<=(p-)/block;i++)
{
if (f.find(1ll*b*inv(t)%p)!=f.end()) return i*block+f[1ll*b*inv(t)%p];
t=1ll*t*v%p;
}
return -;
}
int main()
{
#ifndef ONLINE_JUDGE
freopen("exbsgs.in","r",stdin);
freopen("exbsgs.out","w",stdout);
#endif
a=read(),p=read(),b=read();
while (a)
{
if (p==) printf(b==?"0\n":"No Solution\n");
else if (b==) printf("0\n");
else
{
int t=,ans=;
for (int i=;i<=;i++)
{
t=1ll*t*a%p;
if (t==b) {ans=i;break;}
}
if (!ans)
{
int u=gcd(p,t);
if (b%u==)
{
//a^x/u=b/u (%p/u)
int P=p;b/=u;p/=u;
for (int i=;i<=;i++)
if (P==p) {ans=i-;break;}
else
{
int u=gcd(a,P);
b=1ll*b*inv(a/u)%p;
P/=u;
}
ans+=BSGS(a,b,p);ans=max(ans,);
}
}
if (ans) printf("%d\n",ans);
else printf("No Solution\n");
}
a=read(),p=read(),b=read();
}
return ;
}