P7890题解

wkywkywky · 2022-10-04 22:58:25 · 题解

感觉这题推导挺 trivial，所以决定只讲下一种绕开光速幂和 Index Calculus 算法的做法。

下记 a 在模 p 意义下的离散对数为 \log_g{a}，其中 g 为 p 的一个原根。

不加证明的给出两个显然的引理。

• Lemma 1: \log_g{ab}\equiv(\log_g{a}+\log_g{b})\pmod{\varphi(p)}

• Lemma 2: x(\left\lfloor\dfrac{p}{x}\right\rfloor+1)\equiv x-(p\bmod{x})\pmod{p}

根据引理 1,2 当 x>\sqrt{p} 时有：

所以当 x>\sqrt{p} 时可以 O(1) 递推求出 \log_{g}x 的值。

由 Lemma 1 知 \log_g{x} 为完全加性函数，故只要求出素数点处值。

综上，只需求所有小于 \sqrt{p} 的素数的原根。

考虑 BSGS 算法本质，用 O(B) 预处理，每次询问 O(\frac{p}{B}) 的复杂度。

平衡下复杂度：

令 B=\frac{p}{B}\frac{\sqrt{p}}{\ln{p}}，解得 B=\frac{p^\frac{3}{4}}{\sqrt{\ln{p}}}。

求前 n 个数的离散对数总复杂度为 O(\frac{p^\frac{3}{4}}{\sqrt{\ln{p}}}+n)。

应出题人不放代码，本人不保证这篇题解做法能稳定通过，读者应自行卡常（