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