洛谷 P4195 Spoj3105 Mod（擴充BSGS）

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
ll P,A,B;
unordered_map<ll,int>M;

ll gcd(ll a,ll b){
    
    return !b?a:gcd(b,a%b);
}

ll mypow(ll b){
    
    ll sum=1;
    ll a=A;
    while(b){
         
        if(b&1) sum=sum*a%P;
        a=a*a%P;
        b>>=1;
    } 
    return sum;
}

int main(){
    
    while(scanf("%lld%lld%lld",&A,&P,&B)==3){
        
        if(A==0 && P==0 && B==0) break;
        if(A%P==0){
            
            printf("No Solution\n");
            continue;
        }
        if(B==1) {
            
            printf("0\n");
            continue;
        }
        bool isok=false;
        A%=P;B%=P;
        ll d=1,cnt=0;
        for(ll g=gcd(A,P);g!=1;g=gcd(A,P)){
            
            if(B%g){
                
                printf("No Solution\n");
                isok=true;
                break;
            }
            P/=g;d=d*A/g%P;B/=g;cnt++;
            if(B==d){printf("%lld\n",cnt);isok=true;break;}
        }
        if(isok) continue;
        M.clear();
        int now=B;
        M[now]=1;
        int m=ceil(sqrt(P));
        for(int i=1;i<=m;i++){
            
            now=now*A%P;
            M[now]=i+1;
        }
        now=d;
        ll k=mypow(m);
        for(int i=1;i<=m;i++){
            
            now=now*k%P;
            if(M.count(now)){
                
                isok=true;
                ll ans=i*m-M[now]+cnt+1;
                printf("%lld\n",(ans%P+P)%P);
                break;
            }
        }           
        if(!isok) puts("No Solution");              
    }
    return 0;
}