Description:


已知多项式方程:

\[a_0+a_1x+a_2x^2+...+a_nx^n=0\]

求这个方程在[1,m]内的整数解(n和m均为正整数)。

Input:


第一行包含2个整数n、m,每两个整数之间用一个空格隔开。

接下来的n+1行每行包含一个整数,依次为 \(a_0,a_1,a_2,...,a_n\)

Output:


第一行输出方程在[1,m]内的整数解的个数。
接下来每行一个整数,按照从小到大的顺序依次输出方程在[1,m]内的一个整数解。

Sample Input:


Sample Output:


题解:


一道NOIP数论题/(ㄒoㄒ)/~~

表示自己做这一题只能够想到70分了.....

70分做法:

70分做法还是比较好想的。
显然我们最先想到的就是枚举[1,m]中的每一个数,检查是否为方程的解~~
那么假设我们枚举了x,检查是需要时间的,突然发现可以用数学必修三上的秦九韶算法$O(n)$直接求多项式的值~~
因为a比较大,如果使用高精度肯定会超时(况且还不想写高精度),所以我们人工的对多项式取两个大质数的膜:),如果答案均为0,认为x是原方程的一个解。
代码如下:

100分做法:

接下来要继续优化,我们不妨设方程左边为 \(f(x)\)
我们要么考虑是否能一个 \(f(x_1)\) 推到一个 \(f(x_2)\) ,这样就可以优化时间。

显然有 \(f(x+P)\equiv f(x) \pmod P\)
那么我们就可以只计算 \([1,P]\) 的所有f值,然后就可以推出 \([1, m]\) 的所有f值。
其实还是比较简单的~~
时间复杂度就变成了 \(O(Pn)\) ,我们把质数取小一点多取几个就可以了♪(^∇^*)

我怎么就这么S*,没有想到呢QAQ

代码如下: