暴力做法是对$[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})$。