WC2020 T2 部分选手的 AC 代码内含惊天漏洞是怎么一回事呢？WC2020 T2 这一普及组难度的题相信大家都很熟悉，但是部分选手的 AC 代码内含惊天漏洞是怎么一回事呢，下面就让小编带大家来了解一下吧！

作为出题人，在闲的没事翻选手的 AC 代码的过程中，我发现部分采用求原根的思路选手的提交中求原根的部分没有判 $\gcd(g, p) = 1$（如 幸运观众#1、幸运观众#2、幸运观众#3），这明显是错误的。我在比赛日当天就意识到了这个问题，不过由于种种原因没有尝试把这个错误的做法 hack 掉，同时我对此的印象也仅仅停留在「这可能是一个可以 hack 的点」。

然而后来在实际操作中我发现这个错误的做法貌似在绝大多数情况下均能得到正确的结论，也就是说以下结论很可能是对的：

定理：对于奇素数 $p$，模 $p^a$ 意义下的最小正原根小于 $p$。

那么该如何证明这一结论呢？

引理：对于正整数 $a > 1$ 和奇素数 $p$，模 $p^a$ 意义下的原根均为模 $p$ 的原根。

不妨设 $g$ 是模 $p^a$ 的原根但不是模 $p$ 的原根，则存在 $p - 1$ 的素因子 $d$ 使得 $$ g^{\frac{p - 1}{d}} \equiv 1 \pmod {p} $$ 不妨设上式左端值为 $kp + 1$，则有 $$ \begin{align} g^{p^{a-1} \cdot \frac{p - 1}{d}} = (kp + 1)^{p^{a-1}} = \sum_{i = 0}^{p^{a-1}} \binom{p^{a-1}}{i}(kp)^i \equiv \sum_{i = 0}^{a - 1} \binom{p^{a-1}}{i}(kp)^i \equiv 1 \pmod{p^a} \end{align} $$ 这与我们的假设矛盾。

$a = 2$ 的情形

众所周知模 $p^2$ 的一个完系中有 $(p - 1)\varphi(p - 1)$ 个数是 $p^2$ 原根，同时有 $p\varphi(p - 1)$ 个数是 $p$ 的原根。记后者构成的集合为 $S$。

根据引理，模 $p^2$ 的原根必是模 $p$ 的原根，同时在 $[1, p]$ 中所有 $p$ 的原根都不是 $p^2$ 的原根，由此可知 $[p + 1, p^2]$ 中所有 $p$ 的原根均是 $p^2$ 的原根。

取 $g \in S$ 使得 $1 < g < p$，考虑 $g$ 在模 $p^2$ 意义下的逆 $h$。显然 $h$ 是模 $p$ 的原根，即 $h \in S$，又由于 $h$ 和 $g$ 在模 $p^2$ 下有相同的阶，因此 $h$ 不是 $p^2$ 的原根，即 $1 < h < p$。这与 $gh \equiv 1 \pmod {p^2}$ 矛盾。

综上所述，在 $a = 2$ 时结论时成立的，即 $p^2$ 的最小正原根 $h(p) < p$。

实际上，这篇论文 证明了 $h(p) < p^{0.99}$，有兴趣的选手可以自行了解。

$a > 2$ 的情形

The proof of this part is trivial and left as an exercise to the reader.

那么该如何出数据才能卡这个错误的做法呢？

其实也很简单。我们小学二年级就知道所有形如 $2p^a$ （$p$ 是奇素数）的数都有原根。在数据范围中允许这一类的数存在就可以让错误的算法在枚举到 $2$ 的时候就直接暴毙了。

我赌你的枪里没有子弹

这时候就有的选手要说了，“我就是提前知道这个结果才不判的，你啊，naive！”。

......

你说是，那就是，不狡辩。

以上就是WC2020 T2 部分选手的 AC 代码内含惊天漏洞的全部内容了，大家有什么想法呢，欢迎在评论区告诉小编一起讨论哦！