欢迎光临散文网会员登陆 & 注册

浅谈扩展 BSGS

2023-07-28 19:52 作者:wukaichen888 0人读过 | 我要投稿

听 sbh 大佬讲数论，讲得当然比老师好，很感动，记笔记

给出 $a$ ， $b$ ， $p$ ，求最小非负整数解 $x$ 满足 $a%5Ex%5Cequiv%20b%5C%20(mod%5C%20p)$

其实是个分块算法

先说 BSGS，当 $a$ ， $p$ 互质时的做法

考虑对指数 $x$ 进行分块，显然有解时 $0%5Cle%20x%5Clt%20p$

则令 $t%3D%5Clceil%5Csqrt%7Bp%7D%5Crceil$ ， $x$ 定然能表示为 $i%5Ctimes%20t-j$ ，其中 $1%5Cle%20i%20%5Cle%20t$ ， $1%5Cle%20j%5Cle%20t$

$a%5E%7Bi%5Ctimes%20t-j%7D%5Cequiv%20b%5C%20(mod%5C%20p)$

$a%5E%7Bi%5Ctimes%20t%7D%5Cequiv%20b%5Ctimes%20a%5Ej%5C%20(mod%5C%20p)$

预处理枚举 $j$ 用哈希表将 $b%5Ctimes%20a%5Ej$ 存下

然后枚举 $i$ 判断 $a%5E%7Bi%5Ctimes%20t%7D$ 是否出现

复杂度 $O(%5Csqrt%7Bn%7D)$

不互质就是 Ex_BSGS 惹

$a%5Ex%5Cequiv%20b%5C%20(mod%5C%20p)$ ， $g%3Dgcd(a%2Cp)%5Cgt1$

$a%5E%7Bx-1%7D%5Ctimes%20a%5Cequiv%20b%5C%20(mod%5C%20p)$

$a%5E%7Bx-1%7D%5Ctimes%20%5Cfrac%7Ba%7D%7Bg%7D%5Cequiv%20%5Cfrac%7Bb%7D%7Bg%7D%5C%20(mod%5C%20%5Cfrac%7Bp%7D%7Bg%7D)$

$b%3D1$ 时 $x%3D0$ ，否则如果 $g%5Cnmid%20b$ ，原方程无解

然后继续拆前面的 $a%5E%7Bx-1%7D$ 直到 $a$ ， $p$ 互质

$a%5E%7Bx-k%7D%5Ctimes%5Cfrac%7Ba%5Ek%7D%7B%5Cprod%20g_i%7D%5Cequiv%20%5Cfrac%7Bb%7D%7B%5Cprod%20g_i%7D%5C%20(mod%5C%20%5Cfrac%7Bp%7D%7B%5Cprod%20g_i%7D)$

$a%5E%7Bx-k%7D%5Cequiv%20%5Cfrac%7Bb%7D%7B%5Cprod%20g_i%7D%5Ctimes%5Cfrac%7B%5Cprod%20g_i%7D%7Ba%5Ek%7D%5C%20(mod%5C%20%5Cfrac%7Bp%7D%7B%5Cprod%20g_i%7D)$

然后直接 BSGS，还有一堆特判

一定要用扩欧求逆元（

标签：

浅谈扩展 BSGS的评论 (共条)