「学习笔记」BSGS点击查看目录目录「学习笔记」BSGSBaby-stepGiant-step问题算法例题DiscreteLogging代码P3306[SDOI2013]随机数生成器思路P2485[SDOI2011]计算器思路Matrix思路代码Baby-stepGiant-step问题在\(O(\sqrt{p})\)的时间内求解\[a^x\equivb\pmodp\]其中\(a\perpp\)，方程的解\(x\)满足\(0\lex。算法首先根据费马小定理\(a^{p-1}\equiv1\pmod{p}\)，不难发现\(1\simp-1\)是一个循环节，也就是说只用判断\(1\simp-1\)

(ex)BSGS/（扩展）大步小步算法学习笔记在即将暂时退役之际杀掉了P4195的毒瘤模板题，于是来写篇学习笔记。谨此为我初中三年摆烂的OI生涯画上一个句号。（距离中考还有20天！）BSGSlink求\(a^x\equivb\pmodp\)的非负整数解，其中\(a,p\)互质。算法思路我们不妨令\(t=\lceil{\sqrt{p}\rceil}\)，\(j\ltt\)，\(i\leqt\)原式转化为\(a^{it-j}\equivb\pmodp\)即\(\left(a^t\right)^i\equivb\cdota^j\pmodp\)于是我们可以这么在\(\Theta\left(\sqrt{

简介大步小步(BabyStepGiantStep)算法，可以在\(O(\sqrt{p}\cdotf(p))\)的时间复杂度内（\(f(p)\)为一个大小为\(p\)的映射结构（如map、hashtable）进行单次读取/随机访问的时间复杂度）内解下列关于\(x\)的方程（离散对数方程）：\[a^{x}\equivb\pmod{p}\]其中\(\mathbf{p\in\mathbb{P},a\perpp}\)。思路由于欧拉定理\(a\perpp,a^{b}\equiva^{b\bmod\varphi(p)}\pmod{p}\)，可以得到：\[a^{x\bmod(p-1)}\equiva^{x}\

「学习笔记」BSGS点击查看目录目录「学习笔记」BSGSBaby-stepGiant-step问题算法例题DiscreteLogging代码P3306[SDOI2013]随机数生成器思路P2485[SDOI2011]计算器思路Matrix思路代码Baby-stepGiant-step问题在\(O(\sqrt{p})\)的时间内求解\[a^x\equivb\pmodp\]其中\(a\perpp\)，方程的解\(x\)满足\(0\lex。算法首先根据费马小定理\(a^{p-1}\equiv1\pmod{p}\)，不难发现\(1\simp-1\)是一个循环节，也就是说只用判断\(1\simp-1\)

「学习笔记」BSGS点击查看目录目录「学习笔记」BSGSBaby-stepGiant-step问题算法例题DiscreteLogging代码P3306[SDOI2013]随机数生成器思路P2485[SDOI2011]计算器思路Matrix思路代码Baby-stepGiant-step问题在\(O(\sqrt{p})\)的时间内求解\[a^x\equivb\pmodp\]其中\(a\perpp\)，方程的解\(x\)满足\(0\lex。算法首先根据费马小定理\(a^{p-1}\equiv1\pmod{p}\)，不难发现\(1\simp-1\)是一个循环节，也就是说只用判断\(1\simp-1\)