LUOGU P4195 Spoj3105 Mod

bsgs问题。因为p可能不为质数，所以我们将原先解题的式子变形

每次除以p与a的最大公约数，直到最大公约数为1或b不能整除为止

代码



#include<iostream>

#include<algorithm>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<map>

#define LL long long

using namespace std;

LL a,b,m,p,now,ans;

bool flag;

map<LL,int> mp;

inline LL fast_pow(LL a,LL b){

    LL ret=1;

    LL aa=a;

    for(;b;b>>=1){

        if(b&1) ret=ret*aa%p;

        aa=aa*aa%p;

    }

    return ret;

}

int main(){

    while(~scanf("%lld%lld%lld",&a,&p,&b)){

        if(a==0 && b==0 && p==0) break;

        if(a%p==0){

            puts("No Solution");

            continue;

        }

        if(b==1) {

            puts("0");

            continue;

        }

        flag=false;

        a%=p;b%=p;

        LL t=1,cnt=0;

        for(register int i=__gcd(a,p);i!=1;i=__gcd(a,p)){

            if(b%i){

                puts("No Solution");

                flag=1;

                break;

            }

            p/=i;t=t*a/i%p;b/=i;cnt++;

            if(b==t) {printf("%lld\n",cnt);flag=1;break;}

        }

        if(flag) continue;

        mp.clear();

        now=b;

        mp[now]=0;

        m=ceil(sqrt(p));

        for(register int i=1;i<=m;i++){

            now=now*a%p;

            mp[now]=i;

        }

        now=t;

        LL k=fast_pow(a,m);

        for(register int i=1;i<=m;i++){

            now=now*k%p;

            if(mp[now]){

                flag=true;

                ans=i*m-mp[now]+cnt;

                printf("%lld\n",ans);

                break;

            }

        }

        if(!flag) puts("No Solution");

    }

    return 0;

}

巴特西

LUOGU P4195 Spoj3105 Mod

代码

最新文章

热门文章