UOJ Logo jcvb的博客

博客

noip 2014 day2 T3 jcvb题解

2014-11-09 15:58:42 By jcvb

暴力做法是对$[1,m]$的所有整数在模意义下验证,复杂度$O(nm)$。

取一个质数$P$,对$[0,P-1]$的整数进行验证(模$P$意义下),复杂度是$O(Pn)$。(注意挑选的$P$需要保证$f(x)$在模$P$意义下不会变成零多项式)

然后可以知道模$P$意义下有不超过$n$个解。(拉格朗日定理)

那么对应地,在$[1,m]$中至多只有$n \cdot \left\lceil m/P \right\rceil$个解,对这些解进行验证即可。复杂度$O(n^2m/P)$。

取$P$在$\sqrt{nm}$附近。总复杂度$O(n \sqrt{nm})$。

2333333

2014-10-20 18:35:42 By jcvb

今天是个喜大普奔的好日子!

jcvb Avatar