题解：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$。