扩展 $\tt{BSGS}$ 算法

这道题是 $\tt{exBSGS}$ 的模板题。

先了解一下普通的 扩展 $\tt{BSGS}$ 算法。

已知 $a,b,p$，求最小的正整数 $x$ 满足

$$a^x \equiv b \pmod p$$

其中 $p$ 是质数。

$\tt{BSGS}$ 的思想核心是分块

考虑设 $S=\sqrt p$，那么每个 $x$ 都可以表示为 $nS+m$ 的形式。

对于所有 $(0\le k\le S)$，把 $b\times a^k$ 放到哈希表（也可以放到 $\tt{map}$ ）中。

枚举 $n$ ，然后看是否有满足条件 $m$ 即可。

时间复杂度 $O(\sqrt p)$。

接下来考虑 $\tt{exBSGS}$ 问题。

已知 $a,b,p$，求最小的正整数 $x$ 满足

$$a^x \equiv b\ \mod p$$

其中 $p$ 是任意正整数。

考虑将这个问题转化为普通的 $\tt{BSGS}$ 问题，即将 $p$ 转化为质数。

设 $D=\gcd(a,p)$ 那么如果 $D\nmid b$ 那显然无解。

原式变成

$$\frac{a^x}{D} \equiv \frac{b}{D} \pmod {\frac{p}{D}} $$

取出一个 $a$。

$$a^{x-1}\times \frac{a}{D} \equiv \frac{b}{D} \pmod {\frac{p}{D}} $$

可以继续对 $a^{x-1}$ 进行这样的操作，直到 $D=1$。

得到

$$a^{x-k}\times \frac{a^k}{\prod_{i=1}^k d_i} \equiv \frac{b}{\prod_{i=1}^k d_i} \pmod {\frac{p}{\prod_{i=1}^k d_i}} $$

此时 $p$ 与 $a$ 互质，直接跑普通的 $\tt{BSGS}$ 就可以了。

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
map<int,int> mp;
int kuai(int a,int b,int mod){
    int ans=1;
    for(;b;b>>=1,a=1ll*a*a%mod)if(b&1)ans=1ll*ans*a%mod;
    return ans;
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
void exBSGS(int a,int b,int p){
    a%=p,b%=p;
    mp.clear();
    if(b==1){
        puts("0");
        return;
    }
    int D=gcd(a,p),sum=1,k=0;
    while(D!=1){
        if(b%D){
            puts("No Solution");
            return;
        }
        b/=D,p/=D;
        k++;
        sum=1ll*sum*(a/D)%p;
        if(sum==b){
            printf("%d\n",k);
            return;
        }
        D=gcd(a,p);
    }
    int now=b;
    int S=ceil(sqrt(p));
    mp[now]=1;
    for(int i=1;i<=S;i++){
        now=1ll*now*a%p;
        mp[now]=i+1;
    }
    now=kuai(a,S,p);
    for(int i=1;i<=S;i++){
        sum=1ll*sum*now%p;
        if(mp.find(sum)!=mp.end()){//注意此处不要直接mp[sum]，容易TLE
            printf("%d\n",i*S-mp[sum]+1+k);
            return;
        }
    }
    puts("No Solution");
}
int a,b,p;
int main() {
    while(scanf("%d%d%d",&a,&p,&b)){
        if(!a&&!b&&!p)break;
        exBSGS(a,b,p);
    }
    return 0;
}

提供一种比较简短的实现。详细见代码。
此外，本题现有数据特别弱，务必注意自己的代码正确性。

#include<bits/extc++.h>
using namespace std;
__gnu_pbds::gp_hash_table<int,int> T;
tuple<int,int,int,int> exbsgs(int _p,int a,int _b){
	int p=_p,t=1,b=_b,l=0;
	while(__gcd(a,p)!=1){
		const int g=__gcd(a,p);
		if(b%g) return{l,-1,0,0};
		p/=g; b/=g;
		t=int64_t(t)*a/g%p;
		++l;
	}
	return{l,p,t,b};
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
for(;;){
	int _p,a,_b;
	cin>>a>>_p>>_b;
	if(_p==0) return 0;
	a%=_p;_b%=_p;
	if(_p==1) {cout<<"0\n";continue;}
// else if(_b==1) {cout<<"0\n";continue;}
// else if(a==_b){cout<<"1\n";continue;}
	auto[l,p,t,b]=exbsgs(_p,a,_b);
	int64_t it=1,ima=1,fd;
	const int k=sqrt(p);
	for(int i=0;i<=l;it=it*a%_p,++i)
		if(it==_b){cout<<i<<'\n';goto Ond;}
	if(p==-1) {cout<<"No Solution\n";continue;}
	for(int i=0;i<k;ima=ima*a%p,++i)
		T[ima*b%p]=i;
	fd=ima;
	for(int j=0;j++<=k+1;fd=fd*ima%p)
		if(T.find(t*fd%p)!=T.end()){
			cout<<j*k-T[t*fd%p]+l<<'\n';
			goto End;
		}
	cout<<"No Solution\n";
	End:;T.clear();Ond:;
}}