bsgs

问题一：

若 ( a , p ) = 1 ,    p (a,p)=1,\;p (a,p)=1,p​​ 是素数, 求方程 a x ≡ b ( m o d p ) a^x\equiv b\pmod p ax≡b(modp)​​​ 的（最小非负）解

引理： a k ≡ a k    m o d    p − 1 m o d    p a^k \equiv a^{k \; mod \; p-1} \mod p ak≡akmodp−1modp

即k大于p-1后存在循环节，所以原方程若存在解x，则x<p-1

将x写成带余除法的形式：x=Am-B（和写成Am+B一个道理）

a A m − B ≡ b ( m o d p ) a^{Am-B} \equiv b \pmod p aAm−B≡b(modp)​​ 可化为 a A m ≡ b a B ( m o d p ) a^{Am} \equiv ba^B \pmod p aAm≡baB(modp)​​，1<=A<=p/m, 0<=B<m

枚举B，将 b a B ba^B baB​​ 映射到unordered_map。再枚举A，依次判断是否存在 b a B ba^B baB​ 和当前的 a A m a^{Am} aAm​ 相等，如果相等Aim-B就是答案。时间复杂度O(max{p/m,m})，所以当 $ m=\sqrt p$​​ ​ 时时间复杂度最优。

扩展1：

若 ( a , p ) = 1 ,    p (a,p)=1,\;p (a,p)=1,p​ 不一定是素数, 求方程 a x ≡ b ( m o d p ) a^x\equiv b\pmod p ax≡b(modp)​​ 的（最小非负）解

引理（欧拉定理）：

设 ( a , m ) = 1 (a,m)=1 (a,m)=1 , 则有 a φ ( m ) ≡ 1 ( m o d m ) a^{\varphi(m)} \equiv 1 \pmod m aφ(m)≡1(modm)​

所以有: a k ≡ a k    m o d    φ ( m ) m o d    p a^k \equiv a^{k \; mod \; \varphi(m)} \mod p ak≡akmodφ(m)modp​

如果有解，那么一定存在x小于 φ ( m ) \varphi(m) φ(m)

模板题：P3846 [TJOI2007] 可爱的质数/【模板】BSGS

代码实现：

ll bsgs(ll a, ll b, ll p)  //解a^x=b(mod p)
{
    unordered_map<ll,int> mp;
    a%=p, b%=p;
    if (b==1) return 0;
    
    ll k=sqrt(p+0.5);
    for (int i=0, j=b; i<k; i++)  //枚举B
    {
        mp[j]=i;
        j=j%p*(a%p)%p;
	}
    
    ll num=fpow(a,k,p);
    for (int i=1, j=num; i<=k+2; i++)  //枚举A
    {
        if (mp.find(j)!=mp.end()) return k*i-mp[j];
        j=j%p*(num%p)%p;
	}
    return -1;
}
//注意A，B的范围。A是[ 1,sqrt(p)+2 ]，B是[ 0,sqrt(p) )

拓展2：

若 ( a , p ) = 1 (a,p)=1 (a,p)=1 不一定成立 , 求方程 a x ≡ b ( m o d p ) a^x\equiv b\pmod p ax≡b(modp)​​ 的（最小非负）解

设 ( a , p ) = d (a,p)=d (a,p)=d​​​ ，那么原方程可化为 a c a x − 1 ≡ b d ( m o d p d ) {\frac{a}{c}a^{x-1}}\equiv \frac{b}{d} \pmod {\frac{p}{d}} ca​ax−1≡db​(moddp​)​​​ ，依次类推，直至 ( a , p d c n t ) = 1 (a,\frac{p}{d^{cnt}})=1 (a,dcntp​)=1​​ 为止，然后进行依次一般的bsgs即可

模板题：P4195 【模板】扩展 BSGS/exBSGS

代码实现：

ll gcd(ll a, ll b) { return b==0?a:gcd(b,a%b); }

ll fpow(ll base, ll n, ll mod)
{
	ll ans=1;
	while(n)
	{
		if (n&1) ans=(ans%mod*base%mod)%mod;
		base=(base%mod*base%mod)%mod;
		n>>=1;
	}
	return ans;
}

ll bsgs(ll a, ll b, ll p, ll ad)
{
    map<ll,int> mp;
    a%=p, b%=p;
    
    ll k=sqrt(p+0.5);
    for (int i=0, j=b; i<k; i++)
    {
        mp[j]=i;
        j=j%p*(a%p)%p;
	}
    
    ll num=fpow(a,k,p);
    for (ll i=1, j=num; i<=k+2; i++)
    {
        if ( mp.find(j%p*(ad%p)%p)!=mp.end() ) return k*i-mp[j%p*(ad%p)%p];
        j=j%p*(num%p)%p;
	}
    return -1;
}

ll ex_bsgs(ll a, ll b, ll p)
{
    a%=p, b%=p;
    if (b==1 || p==1) return 0;
    
    ll cnt=0;
    ll d, ad=1;
    while((d=gcd(a,p))^1)  //一直除到gcd(a,p)=1为止
    {
        if (b%d) return -1;  //除不下去就无解
        cnt++;  //记录除了几次
        b/=d, p/=d;
        ad=ad%p*(a/d)%p;
        if (ad==b) return cnt;
    }

    ll ans=bsgs(a,b,p,ad);
    if (ans==-1) return -1;
    return ans+cnt;
}