题解 P4195 【【模板】exBSGS/Spoj3105 Mod】

· · 题解

今天才发现原来\rm{BSGS}有两种写法……并且觉得剩下的题解讲的都讲的不是很全的样子233。

其实本质上，当p不为素数时，我们无法进行朴素\rm{BSGS}的原因是我们的欧拉定理a^{\varphi(p)} \equiv b(\bmod p) 只能处理(a,p)=1的情况。那么我们知道，朴素的\rm{BSGS}的关键在于，可以保证最小解是有界的——x一定在[1,\varphi(p)]中。所以最后BSGS的复杂度才会是\Theta(\sqrt{\varphi(p)}) 的——比如说比较常见的p是素数的情况下，时间复杂度为\Theta(p)。

那么也就是说，我们只需要进行一些操作，保证(a,p)=1 即可。

我们思考，对于同余式a^x\equiv b~(\bmod p)而言，我们先假定(a,p)>1 。而此时如果有((a,p), b)=1，那么说明此式只有可能在x=0,b=1 的时候有解——这个结论是平凡的。因为假设我们把它展开成a\cdot a^{x-1} +kp=b 的形式，必须要有(a,p) ~|~ b的情况下，才能保证a^{x-1}和k 都是整数。

那么对于(a,p)>1且(a,p)~|~b ，我们令原式变成

a^{x-1}\cdot \frac{a}{(a,p)} \equiv \frac{b}{(a,p)} (\bmod \frac{p}{(a,p)})

的样子，如果此时(a^{x-1},\frac{p}{(a,p)})=1 的话，我们就直接解

a^{x-1}\equiv \frac{\frac{b}{(a,p)}} {\frac{a}{(a,p)} }(\bmod \frac{p}{(a,p)})

这个方程即可。否则我们继续分解直至(p',a)=1。

那么此时有个问题需要注意，就是如果们在解这个方程时，出现了

(a^{x-1}, \frac{p}{(a,p)})\nmid \frac{\frac{b}{(a,p)}} {\frac{a}{(a,p)} }

的情况，那我们需要特判并return -1 ；另一种情况，如果我们出现了

a^{x-1}\equiv \frac{\frac{b}{(a,p)}} {\frac{a}{(a,p)} } \equiv1(\bmod \frac{p}{(a,p)})

的情况，也需要特判并输出此k（此时同余式左边是a^{x-k}，因为a^{x-k}\equiv1~(\bmod p)所以直接输出k），不过也有可能不需要，完全看你写的BSGS能不能判断x=0的情况……一般情况下不能。

算法流程大体就是这些。有些需要注意的是，BSGS有两种写法。我的这种写法是小步为a^j，大步为a^{-im}b。此时由于\bold{p}不再是素数，所以不能用费马小定理，需要我们用exgcd的方法求逆元，包括但不限于\frac{b}{(a,p)}的逆元和a^{-im}。

如果不是很懂怎么写BSGS的，可以看这里：Link

以下是完整版代码：


#include <map>
#include <cmath>
#include <cstdio>
#include <iostream>
#include <unordered_map>

#define ll long long

using namespace std ; 
unordered_map<ll, int> H ;
int N, M, P, ans ; // N ^x = M (mod P)

inline ll gcd(ll a, ll b){
    if (!b) return a ;
    return gcd(b, a % b) ;
}
inline ll expow(ll a, ll b, ll mod){
    ll res = 1 ;
    while (b) res = ((b & 1)?res * a % mod : res), a = a * a % mod, b >>= 1 ;
    return res ;
}
inline ll exgcd(ll &x, ll &y, ll a, ll b){
    if (!b){ x = 1, y = 0 ; return a ; }
    ll t = exgcd(y, x, b, a % b) ; y -= x * (a / b) ; return t ;
}
inline ll BSGS(ll a, ll b, ll mod, ll qaq){
    H.clear() ; ll Q, p = ceil(sqrt(mod)), x, y ; 
    exgcd(x, y, qaq, mod), b = (b * x % mod + mod) % mod, 
    Q = expow(a, p, mod), exgcd(x, y, Q, mod), Q = (x % mod + mod) % mod ;
    for (ll i = 1, j = 0 ; j <= p ; ++ j, i = i * a % mod)  if (!H.count(i)) H[i] = j ;
    for (ll i = b, j = 0 ; j <= p ; ++ j, i = i * Q % mod)  if (H[i]) return j * p + H[i] ; return -1 ;
}
inline ll exBSGS(){
    ll qaq = 1 ;
    ll k = 0, qwq = 1 ; 
    if (M == 1) return 0 ; 
    while ((qwq = gcd(N, P)) > 1){
        if (M % qwq) return -1 ;
        ++ k, M /= qwq, P /= qwq, qaq = qaq * (N / qwq) % P ;
        if (qaq == M) return k ;
    }
    return (qwq = BSGS(N, M, P, qaq)) == -1 ? -1 : qwq + k ;
}                    
int main(){
    while(cin >> N){
        scanf("%d%d", &P, &M); if (!N && !M && !P) return 0 ;
        N %= P, M %= P, ans = exBSGS() ; if (ans < 0) puts("No Solution") ; else cout << ans << '\n' ;
    }
}