【数论】BSGS

题单介绍

**2020.3.18 upd** : 添加P5345、P4454两题 **2020.5.16 upd** : 添加CF1106F **2022.2.21** : 添加P4028 BSGS(baby-step gaint-step),即大步小步算法。常用于求解离散对数问题。形式化地说,该算法可以在 $O(\sqrt p)$ 的时间内求解 $$a^x \equiv b\ (\bmod \ p)$$ 其中$a \perp p $ 。方程的解满足 $0\leq x< p$。(在这里需要注意,只要 $a \perp p $ 就行了,不要求 $p$ 是素数) 详见[oi-wiki](https://oi-wiki.org/math/bsgs/)

题目列表

  • [TJOI2007] 可爱的质数/【模板】BSGS
  • [SDOI2011] 计算器
  • 多少个 1?
  • [SDOI2013] 随机数生成器
  • 【模板】扩展 BSGS/exBSGS
  • 【XR-1】快乐肥宅
  • [CQOI2018] 破解D-H协议
  • Lunar New Year and a Recursive Sequence
  • New Product