这道题把O(m)的算法优化一下即可AC
也就是在计算的时候
只把取值为0的x记录下来
再判断这个值是否在每个模数下都出现
就AC了
(也许是数据水了

我来说一下这个题目怎么做. sujiao作为出题人, 如果有空最好也发一下说明, 估计小朋友等不动年鉴了...

(1) 先说一下O(nm)的算法. 大家应该都知道可以把所有系数A_i都mod一个大素数, 之后在O(n)内判定一个数字x是不是解的方法了. 那么直接用这样的方法可以判定所有的数字, 时间复杂度是O(nm)的, 在noip现场应该可以得到期望得分70分. 在加强版的题目中应该可以得到40分.

(2) 再说一下O(m)的算法, 这个算法应该是可以在noip现场轻松通过所有数据的. 因为O(nm)会超时, 那么我们不妨只考虑1<=x<=K<m的所有数字是不是解, 时间复杂度O(nk), 这里k需要自己选取. 之后对于1<=x<=m, 我们可以用已经算出来的x%k的结果, 去很大概率估计x是不是解. 有着更强正确率的方法是, 寻找若干个不同的k, 甚至最好选取k个大小相差不多的素数, 比如说我们选取10个k0,k1,...,k9. 那么x是不是根就利用x%ki来判定.

(3) O(n^3+nsqrt(m))的算法, 我们选取素数p0,p1满足p0^2>=m,p1^2>m.然后在mod(pi)意义下算出来0<=x<pi的所有根, 这一部分的时间复杂度是O(nsqrt(m))的. 可以说明, 找到的两组根都不超过n个, 我们记为t1,t2,...,tu和s1,s2,...,sv. 那么我们断言原问题的可行根x一定可以通过某一个ti和某一个sj组合得到, 再利用O(n)的方法判定是不是根. 这一部分的时间复杂度是O(n^3), 这样可以通过所有的数据.

最后散扯一句, 利用heoi2012的Akai的数学作业一题的方法, 可以在noip现场骗到满分. heoi2012这个题目当年就是我出的, 所以过一段时间我就在vijos上挂出来. [等我找到遗失的数据之后...=_=...]