题解 P4195 【【模板】exBSGS/Spoj3105 Mod】
皎月半洒花
2019-02-22 21:10:55
今天才发现原来$\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$](http://www.orchidany.cf/2019/02/06/BSGS-junior/#more)
以下是完整版代码：
```cpp
#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' ;
}
}
```