BZOJ2480: Spoj3105 Mod

题解:

EXBSGS裸题.

代码:

#include<cmath>
#include<cstdio>
#include<cctype>
#include<climits>
#include<cstring>
#include<cstdlib>
#include<iostream>
#include<algorithm>
using namespace std;
 
typedef long long ll;
inline ll gcd(ll a,ll b){
    return(!b)?a:gcd(b,a%b);
}
 
inline ll pow(ll x,ll y,ll p){
    ll re=1,t=x;
    for(;y;y>>=1,t=t*t%p)
        if(y&1)
            re=re*t%p;
     
    return re;
}
 
inline void exgcd(ll a,ll b,ll&d,ll&x,ll&y){
    if(!b){
        d=a;
        x=1;
        y=0;
    }
    else{
        exgcd(b,a%b,d,y,x);
        y-=x*(a/b);
    }
}
 
inline ll inv(ll a,ll p){
    ll d,x,y;
    exgcd(a,p,d,x,y);
    x=(x%p+p)%p;
    return x;
}
 
struct Hashset{
    static const int mod=23333;
    int head[mod],next[50010],f[50010],v[50010],ind;
    inline void reset(){
        ind=0;
        memset(head,-1,sizeof head);
    }
    inline void insert(int x,int _v){
        int ins=x%mod;
        for(int j=head[ins];j!=-1;j=next[j])
            if(f[j]==x){
                v[j]=min(v[j],_v);
                return;
            }
        f[ind]=x;
        v[ind]=_v;
        next[ind]=head[ins];
        head[ins]=ind++;
    }
    inline int operator[](int x){
        int ins=x%mod;
        for(int j=head[ins];j!=-1;j=next[j])
            if(f[j]==x)
                return v[j];
        return -1;
    }
}M;
 
inline ll BSGS(ll c,ll a,ll b,ll p){
    ll m=ceil(sqrt(p)),ct=c,t=1;
    M.reset();
    for(int i=0;i<m;++i,(ct*=a)%=p,(t*=a)%=p)
        M.insert(ct,i);
    t=inv(t,p);
    for(int i=0;i*m<p;++i,(b*=t)%=p)
        if(M[b]!=-1)
            return i*m+M[b];
    return -1;
}
 
int main(){
#ifndef ONLINE_JUDGE
    freopen("tt.in","r",stdin);
#endif
 
    ll a,p,b;
    int i,j;
    while(scanf("%lld%lld%lld",&a,&p,&b)!=EOF&&(a+p+b)){
        ll t=1;
        bool ok=0;
        for(i=0;i<100;++i,(t*=a)%=p)
            if(t==b){
                printf("%d\n",i);
                ok=1;
                break;
            }
        ll _gcd;
        if(!ok){
            int tim=0;
            bool nosol=0;
            ll c=1;
            while((_gcd=gcd(a,p))!=1){
                if(b%_gcd){
                    puts("No Solution");
                    nosol=1;
                    break;
                }
                ++tim;
                p/=gcd(a,p);
                (b/=gcd(a,p))%=p;
                (c*=(a/gcd(a,p)))%=p;
            }
            if(!nosol){
                ll ans=BSGS(c,a,b,p);
                if(ans==-1)
                    cout<<"No Solution"<<endl;
                else
                    cout<<ans+tim<<endl;
            }
        }
    }
    return 0;
}