【数论】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


  1. P3846 - 【模板】BSGS / [TJOI2007] 可爱的质数
  2. P2485 - [SDOI2011] 计算器
  3. P4884 - 多少个 1?
  4. P3306 - [SDOI2013] 随机数生成器
  5. P4195 - 【模板】扩展 BSGS / exBSGS
  6. P5345 - 【XR-1】快乐肥宅
  7. P4454 - [CQOI2018] 破解D-H协议
  8. CF1106F - Lunar New Year and a Recursive Sequence
  9. P4028 - New Product