BSGS模版玄关求调

#include<bits/stdc++.h>
using namespace std;
#define int long long
int a,p,b;
map<int,int> mp;
inline pair<int,int> exgcd(int a,int b,int c){
    if(b==0){
        int x=c/a,y=0;
        return {x,y};
    }
    pair<int,int> k=exgcd(b,a%b,c);
    int x=k.second,y=k.first-a/b*x;
    return {x,y};
}
inline int qpow(int a,int b){
    int ans=1,base=a;
    while(b){
        if(b&1){
            ans*=base;
            ans%=p;
        }
        base*=base;
        base%=p;
        b>>=1;
    }
    return ans;
}
inline void work(){
    if(a==0&&p==0&&b==0) exit(0);
    mp.clear();
    int sqr=sqrt(p),res=1;
    for(int i=0;i<=sqr-1;i++){
        mp[res]=i;
        cerr<<res<<" "<<i<<endl;
        res=res*a;
        res%=p;
        if(b%p==1){
            cout<<0<<"\n";
            return ;
        }
        if(mp[b%p]){
            cout<<mp[b%p]<<"\n";
            return ;
        }
    }
    cerr<<"--------------"<<endl;
    cout<<qpow(a,sqr)<<" ";
    int now=exgcd(qpow(a,sqr),p,1).first,base=now;
    cout<<qpow(a,sqr)*now<<endl;
    for(int k=1;k*sqr<p;k++){
        cerr<<(b*now)%p<<" "<<now<<" "<<k<<endl;
        if((b*now)%p==1){
            cout<<(k*sqr)%p<<"\n";
            return ;
        }
        if(mp[(b*now)%p]){
            cout<<(mp[(b*now)%p]+now)%p<<"\n";
            return ;
        }
        now*=base;
        now%=p;
    }
    cout<<"No Solution"<<"\n";
}
signed main(){
    while(1){
        cin>>a>>p>>b;
        work();
    }
}