BSGS&&ExBSGS

BSGS&&ExBSGS

BSGS 和 ExBSGS 都是用于解决形如形如下式的高次同余方程的。

[a^xequiv b (mod p) ]

同样的先考虑a，p为质数的情况。

令：

[x=i*t-j ]

那么：

[a^xequiv b (mod p) iff a^{i*t-j}equiv b (mod p) iff a^{i*t}equiv b*a^j (mod p) ]

可以对于每一个j∈[0,t-1]，把右边式子的结果用map存下（模p意义下）。

假设i枚举的上界为T，那么可以枚举i∈[0,T]，一次把左边式子的结果在map中查询即可。

实际上(T_{max}=（p-1）/ t)。

证明：

[∵ a，p互质\ ∴ a^{phi(p)}equiv 1 (mod p)\ ∴ 每经过phi(p)就会出现之前出现过的答案，即循环节。\ ∴ x=i*t≤phi(p)≤p-1\ ∴ i≤frac{p-1}{t} ]

基于此，当t取 根号p 时，时间复杂度最低。

当a，p不一定互质时，需要用到ExBSGS。

[令： d_0=1 d_1=gcd (a,p)\ 则 frac{a^x}{d_1}equiv frac{b}{d_1} (mod frac{p}{d_1})\ iff a^{x-1}*frac{a}{d_1}equiv frac{b}{d_1} (mod frac{p}{d_1})\ 如上继续定义： d_i=gcd (a,frac{p}{prod_{j=0}^{i-1}d_{j}}) ]

若d[T+1]恰好第一次等于1，则此时方程可写为：

[a^{x-T}*frac{a^T}{prod_{i=1}^{T}d_i}equiv frac{b}{prod_{i=1}^{T}d_i} (mod frac{p}{prod_{i=1}^{T}d_i}) ]

发现此时可以直接用BSGS求解！

若过程中存在不能整除的现象，则判定为无解。

map<int,int> mp;
int a,b,P,ans;

IL void ExBSGS() {
    RG int i,T,cnt=0,val,now=1,gcd=getgcd(a,P);
	if(b==1){puts("0");return;}
    while(gcd>1) {
        if(b%gcd) {puts("No Solution");return;};
		++cnt,b/=gcd,P/=gcd,now=now*(a/gcd)%P;
        gcd=getgcd(a,P);
    }
    T=sqrt((DB)P)+1,val=b,mp.clear();
    for(i=0;i<T;++i) mp[val]=i,val=val*a%P;
    a=quick_pow(a,T),val=now;
    for(i=0;i<=T;++i) {
        if(mp.find(val)!=mp.end())
            if(mp[val]>=0&&i*T-mp[val]>=0) {printf("%lld
",i*T-mp[val]+cnt);return;}
        val=val*a%P;
    }
	puts("No Solution");
    return;
}