#擴充BSGS#POJ 3243 Clever Y 洛谷 4195 【模（mú）闆】exBSGS SPOJ 3105 MOD

題目

多組資料，已知數 a , p , b a,p,b a,p,b，求滿足 a x ≡ b ( m o d p ) a^x\equiv b\pmod p ax≡b(modp)的最小自然數 x x x。

分析

由于 p p p可能不是素數，是以BSGS失效了，但是因為 a c ≡ b c ( m o d d c ) ac\equiv bc\pmod {dc} ac≡bc(moddc)，那麼 a ≡ b ( m o d d ) a\equiv b\pmod d a≡b(modd)，是以可以先消去因子，那麼可以轉換成BSGS，然而由于 x ≤ c n t x\leq cnt x≤cnt的情況很有可能，是以先要特判

代碼

#include <cstdio>
#include <cctype>
#include <cmath>
#include <cstring>
#define rr register
using namespace std;
const int p=41777;
struct hash{
	struct node{int y,w,next;}e[p]; int hs[p],tot;
	inline void clear(){memset(hs,0,sizeof(hs)); tot=0;}
	inline void add(int x,int w){e[++tot]=(node){x,w,hs[w%p]},hs[w%p]=tot;}
	inline signed locate(int x){
		for (rr int j=hs[x%p];j;j=e[j].next)
		    if (e[j].w==x) return e[j].y;
		return -1;
	}
}h;
inline signed iut(){
    rr int ans=0; rr char c=getchar();
    while (!isdigit(c)) c=getchar();
    while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
    return ans;
}
inline void print(int ans){
    if (ans==-1) {printf("No Solution"); return;}
    if (ans>9) print(ans/10);
    putchar(ans%10+48);
}

inline signed mo(int a,int b,int mod){return a+b>=mod?a+b-mod:a+b;}
inline signed gcd(int a,int b){return b?gcd(b,a%b):a;}
inline signed bsgs(int a,int b,int mod){
    h.clear();
    rr int g=gcd(a,mod),t1=1,d=1,t=sqrt(mod)+1,cnt=0;
    while (g>1){
    	if (b%g) return -1;
    	b/=g,mod/=g,d=1ll*a/g*d%mod,++cnt,g=gcd(a,mod);
    	if (b==d) return cnt;
    }
    for (rr int j=0;j<t;++j)
        h.add(j,1ll*b*t1%mod),t1=1ll*t1*a%mod;
    a=t1,t1=d;
    if (!a) return !b?1:-1;
    for (rr int i=0;i<=t;++i){
        rr int j=h.locate(t1);
        if (j>=0&&1ll*i*t>=j) return 1ll*i*t+cnt-j;
        t1=1ll*t1*a%mod;
    }
    return -1;
}
signed main(){
    while (1){
        rr int a=iut(),mod=iut(),b=iut();
        if (!a&&!b&&!mod) return 0;
        print(bsgs(a%mod,b%mod,mod)),putchar(10);
    }
}