BSGS-Senior·扩展的BSGS


$\rm{0x01\quad Preface}$

$emmm$严格来讲,不应该被算到一个模板里面。因为在我看来模板是人构造出来的,但是这个算法应该是一个解决问题的$process$…更像是在解一道数学题,如果$BSGS$是定理的话,$exBSGS$更像是一个不断转化的过程233(手动@lxa并且溜

$\rm{0x02\quad Algorithm~Process}$

今天才发现原来$\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 $即可$^{[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$的情况……一般情况下不能。

此时由于$\boldsymbol{p}$不再是素数,所以不能用费马小定理,需要我们用$exgcd$的方法求逆元,包括但不限于$\frac{b}{(a,p)}$的逆元和$a^{-im}$。

以下是完整版代码:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50

#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' ;
}
}

$\rm{0x03\quad Afterword}$

今天才知道原来$BSGS$有两种写法qaq

$zyf2000$好像和我写的$BSGS$对“大步”和“小步”的定义不是很一样…于是最后还是自己$\rm{yy}$的233

$\rm{Reference}$

-------------本文结束感谢您的阅读-------------