WA on #11

输出了 No Solution

#include <unordered_map>
#include <algorithm>
#include <iostream>
#include <cstdio>
#include <cmath>

#define int long long

using namespace std;
int a,p,b;

int quickpow(int a,int k,int MOD) {
    int res=1ll;
    while (k) {
        if (k&1) res=res*a%MOD;
        a=a*a%MOD,k>>=1;
    }
    return res;
}

unordered_map<int,int> mp;

int BSGS(int a,int b,int p,int k) {
    mp.clear();
    int block=sqrt(p),mul=1ll;
    for (int i=0;i<block;i++) mp[b*mul%p]=i,mul=mul*a%p;
    mul=k; int tmul=quickpow(a,block,p);
    for (int i=1;i<=block;i++) {
        mul=mul*tmul%p;
        if (mp.count(mul)) return block*i-mp[mul];
    }
    return -1;
}

int exBSGS(int a,int b,int p) {
    a%=p,b%=p;
    if (b==1 or p==1) return 0;
    int tmp=1ll,cnt=0;
    while (__gcd(a,p)!=1) {
        int d=__gcd(a,p);
        if (b%d) return -1;
        b/=d,p/=d,tmp=tmp*a/d%p,++cnt;
        if (tmp==b) return cnt;
    }
    int res=BSGS(a,b,p,tmp);
    return res==-1?-1:res+cnt;
}

signed main() {
    while (1) {
        scanf("%lld%lld%lld",&a,&p,&b);
        if (!a and !p and !b) break;
        int ans=exBSGS(a,b,p);
        if (ans==-1) printf("No Solution\n");
        else printf("%lld\n",ans);
    }
    return 0;
}