WC2020 T2 部分选手的 AC 代码内含惊天漏洞是怎么一回事呢?WC2020 T2 这一普及组难度的题相信大家都很熟悉,但是部分选手的 AC 代码内含惊天漏洞是怎么一回事呢,下面就让小编带大家来了解一下吧!
作为出题人,在闲的没事翻选手的 AC 代码的过程中,我发现部分采用求原根的思路选手的提交中求原根的部分没有判
然而后来在实际操作中我发现这个错误的做法貌似在绝大多数情况下均能得到正确的结论,也就是说以下结论很可能是对的:
定理:对于奇素数
,模 意义下的最小正原根小于 。
那么该如何证明这一结论呢?
引理:对于正整数
和奇素数 ,模 意义下的原根均为模 的原根。
不妨设
的情形
众所周知模
根据引理,模
取
综上所述,在
实际上,这篇论文 证明了
的情形
The proof of this part is trivial and left as an exercise to the reader.
那么该如何出数据才能卡这个错误的做法呢?
其实也很简单。我们小学二年级就知道所有形如
我赌你的枪里没有子弹
这时候就有的选手要说了,“我就是提前知道这个结果才不判的,你啊,naive!”。
......
你说是,那就是,不狡辩。
以上就是WC2020 T2 部分选手的 AC 代码内含惊天漏洞的全部内容了,大家有什么想法呢,欢迎在评论区告诉小编一起讨论哦!