专栏文章

基于 Farey 序列的 O(1) 在线模逆元，离散对数，模幂，二次剩余

bbsdsdb
算法·理论参与者 12已保存评论 13

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
13 条
当前快照
2 份
快照标识符
@mkh57rn1
此快照首次捕获于
2026/01/17 01:19
上个月
此快照最后确认于
2026/02/13 01:27
6 天前
查看原文
https://maspypy.com/o1-mod-inv-mod-pow
记 x≡y(modP)x\equiv y\pmod P 为 x≡y(P)x\equiv y(P)。

Farey 序列

记 FnF_n 为 nn 阶 Farey 序列，就是所有分母不超过 nn 的既约真分数带上 01\frac01 和 11\frac11 排序组成的序列，如 F5=[01,15,14,13,25,12,35,23,34,45,11]F_5=[\frac01,\frac15,\frac14,\frac13,\frac25,\frac12,\frac35,\frac23,\frac34,\frac45,\frac11]。
引理
对任意 v∈[0,1],n∈Z>0v\in[0,1],n\in\Z_{>0} 存在 pq∈Fn\frac pq\in F_n 使得 ∣v−pq∣≤1qn|v-\frac pq|\le\frac1{qn}。符合的 pq\frac pq 一定是 max⁡(Fn∩[0,v])\max(F_n\cap[0,v]) 或者 min⁡(Fn∩[v,1])\min(F_n\cap[v,1])。
证
第一部分，{x}≔x−⌊x⌋\{x\}\coloneqq x-\lfloor x\rfloor。将 {{iv}:i∈[0,n],i∈Z}\{\{iv\}:i\in[0,n],i\in\mathbb Z\} 排序，易得定存在 0≤i<j≤n0\le i<j\le n 使得 ∣{jv}−{iv}∣≤1n|\{jv\}-\{iv\}|\le\frac1n。令 q≔j−i,p≔⌊jv⌋−⌊iv⌋q\coloneqq j-i,p\coloneqq\lfloor jv\rfloor-\lfloor iv\rfloor。
∣qv−p∣=∣⌊jv⌋+{jv}−⌊iv⌋−{iv}−p∣≤1n|qv-p|=|\lfloor jv\rfloor+\{jv\}-\lfloor iv\rfloor-\{iv\}-p|\le\frac1n
第二部分，不妨设我们找到的 pq<v\frac pq<v。如果 (pq,v)(\frac pq,v) 之间还有 FnF_n 中的 p′q′\frac{p'}{q'}，那么 v−pq>p′q′−pq≥1qq′≥1qnv-\frac pq>\frac{p'}{q'}-\frac pq\ge\frac1{qq'}\ge\frac1{qn} 从而矛盾。
下面三种算法，都是先找到 ∣xP−pq∣≤1qn|\frac xP-\frac pq|\le\frac1{qn} 的 pq\frac pq，就有 ∣qx−pP∣≤Pn|qx-pP|\le\frac Pn，t≔qx mod P∈[−Pn,Pn]t\coloneqq qx\bmod P\in[-\frac Pn,\frac Pn]。
怎么找 pq\frac pq 呢？因为 FnF_n 中数两两之差大于 1n2\frac1{n^2}，故 ⌊n2pq⌋\lfloor\frac{n^2p}{q}\rfloor 互不相同，把所有这些值存起来然后用 ⌊n2xP⌋\lfloor\frac{n^2x}{P}\rfloor 找前驱后继即可。这需要 O(n2)\Omicron(n^2) 的时间。

O(P23)−O(1)\Omicron(P^{\frac23})-\Omicron(1) 逆元

求 x−1 mod Px^{-1}\bmod P，先将所有可能的 tt 的 t−1t^{-1} 预处理出来（离线 O(1)\Omicron(1) 逆元），然后 x−1≡qt−1(P)x^{-1}\equiv qt^{-1}(P)。
O(Pn+n2)−O(1)\Omicron(\frac Pn+n^2)-\Omicron(1)，取 n∼P13n\sim P^{\frac13} 即可做到 O(P23)−O(1)\Omicron(P^{\frac23})-\Omicron(1)。
示例代码

O(P3/4log⁡1/2(P))−O(1)\Omicron(\frac{P^{3/4}}{\log^{1/2}(P)})-\Omicron(1) 离散对数

令 gg 为 PP 的原根，log⁡(x)\log(x) 表示 gg 为底的离散对数，有 log⁡(−1)=P−12\log(-1)=\frac{P-1}2。首先要知道预处理出 [1,m][1,m] 中所有数的对数的复杂度为
{O(Pmlog⁡m),m≤PO(P3/4log⁡1/2(P)+m),otherwise\begin{cases} \Omicron\left(\sqrt\frac{Pm}{\log m}\right),&m\le\sqrt P\\ \Omicron\left(\frac{P^{3/4}}{\log^{1/2}(P)}+m\right),&\text{otherwise} \end{cases}
Info
m≤Pm\le\sqrt P 时，考虑先对所有范围内质数的离散对数求解。发现一般的 BSGS 的 log⁡(x)\log(x) 实际上是固定 BB 然后求解整数对 (y,z)(y,z) 使得
y≤PBz<B(gB)y≡xgz(P)y\le\frac PB\\ z<B\\ {(g^B)}^y\equiv xg^z(P)
由于有 π(m)\pi(m) 次查询，左边要 PB\frac PB 次哈希表插入，右边要 π(m)⋅B\pi(m)\cdot B 次哈希表查找，令 B≔Pπ(m)B\coloneqq\sqrt{\frac P{\pi(m)}} 即可。
有了所有质数的对数之后，利用 log⁡(pq)≡log⁡(p)+log⁡(q)(P−1)\log(pq)\equiv\log(p)+\log(q)(P-1) 即可线性筛得出 mm 以内所有数的离散对数。
m≥Pm\ge\sqrt P 时，先求出 [1,n][1,\sqrt n] 以内的离散对数，然后求 log⁡(x)\log(x) 时，令 P=:kx+rP=:kx+r 则
log⁡(x)≡log⁡(−r)−log⁡(k)≡P−12+log⁡(r)−log⁡(k)(modP−1)\log(x)\equiv\log(-r)-\log(k)\equiv\frac{P-1}2+\log(r)-\log(k)\pmod{P-1}
递推即可。
由于 n2≤Pn^2\le P，预处理 [1,Pn][1,\frac Pn] 上的离散对数，那么 [−Pn,−1][-\frac Pn,-1] 的也同时可以求出来。log⁡(x)≡log⁡(tq)≡log⁡(t)−log⁡(q)(P−1)\log(x)\equiv\log(\frac tq)\equiv\log(t)-\log(q)(P-1)。于是复杂度为 O(n2+P3/4log⁡1/2(P)+Pn)−O(1)\Omicron(n^2+\frac{P^{3/4}}{\log^{1/2}(P)}+\frac Pn)-\Omicron(1)，取 n∼P13n\sim P^{\frac13} 即为 O(P3/4log⁡1/2(P))−O(1)\Omicron(\frac{P^{3/4}}{\log^{1/2}(P)})-\Omicron(1)。

O(P3/4log⁡1/2(P))−O(1)\Omicron(\frac{P^{3/4}}{\log^{1/2}(P)})-\Omicron(1) 模幂

ab≡gblog⁡(a)(P)a^b\equiv g^{b\log(a)}(P)，再预处理 gg 的光速幂即可。

O(P3/4log⁡1/2(P))−O(1)\Omicron(\frac{P^{3/4}}{\log^{1/2}(P)})-\Omicron(1) 二次剩余

设 gg 是 PP 的一个原根，现在求解方程 x2≡a(modP)x^2\equiv a\pmod P。将 aa 表示为 gk mod Pg^k\bmod P。如果 kk 是偶数那么 gk2 mod Pg^{\frac k2}\bmod P 是一个解。否则 aa 不是二次剩余。

评论

共 13 条评论，欢迎与作者交流。

正在加载评论...