题解：P2312 [NOIP 2014 提高组] 解方程

· · 题解

本篇题解不再给出完整代码，想要的同学可以看这篇，里面详细讲解了整道题的思路和代码可能出现的坑点。

回到这里。令等号左边的式子为 f(x)，则当 x \in [1,m] 为解时，有 f(x)=0，也就必然有 f(x) \bmod p=0，其中 p 为我们选取的模数。

反过来，当 f(x) \bmod p=0 时，不一定有 f(x)=0。我们只有尽可能地选取合适的模数，来降低出错的概率。这就有几分玄学的意味了——我们得祈祷出题人不卡我们使用的模数！

那么，存不存在一种方式，使得时间复杂度不大幅提升的同时，正确率大幅提高呢？

有的，这就是我们今天要介绍的另一种写法——双模数。

首先，我们得明白为什么选取单一模数容易被卡。原因在于，出题人可以很方便地令 f(x)=np，其中 n \in N。在这种情况下，f(x) \bmod p=0，但 f(x) \neq 0。

接下来，我们考虑如何改善这种状况。他出题人能卡一个模数，那两个呢？三个？四个……只要我选取的多个模数有一个没有被卡，我就可以确保正确。感性认知一下，这样做的正确率要远高于单一模数。

然而，模数太多也会有一个问题——常数大了。所以，在解决实际问题时，我们往往选取两个模数而非更多，这样既可以提高正确率，又不至于让常数复杂度太大。

具体地，我们应当选取两个不同的模数 p1,p2，检查某一 x 是否为解时，应当检查 f(x) \bmod p1 和 f(x) \bmod p2 是否同时为 0。