现有一个一元高阶方程:
a 0 + a 1 ∗ x + a 2 ∗ x 2 + . . . + a n ∗ x n = 0 a0+a1*x+a2*x^2+...+an*x^n=0 a0+a1∗x+a2∗x2+...+an∗xn=0
现给出数字 m m m,求出此方程在 [ 1 , m ] [1,m] [1,m] 以内的整数解。
第一行包含 2 2 2 个整数 n 、 m n、m n、m,每两个整数之间用一个空格隔开。 接下来的 n + 1 n+1 n+1 行每行包含一个整数,依次为 a 0 , a 1 , a 2 , . . . , a n a0,a1,a2,...,an a0,a1,a2,...,an。
第一行输出方程在 [ 1 , m ] [1,m] [1,m] 内的整数解的个数。 接下来每行一个整数,按照从小到大的顺序依次输出方程在 [ 1 , m ] [1,m] [1,m] 内的一个整数解。
【数据范围】
对于 100 % 100\% 100%的数据, 0 < n ≤ 100 , ∣ a i ∣ ≤ 1 0 10000 , a n ≠ 0 , m ≤ 1000000 0<n≤100,|ai|≤10^{10000},an≠0,m≤1000000 0<n≤100,∣ai∣≤1010000,an=0,m≤1000000
这道题显然不能打暴力, 但可以用秦九韶算法将 a 0 + a 1 ∗ x + a 2 ∗ x 2 + . . . + a n ∗ x n = 0 a0+a1*x+a2*x^2+...+an*x^n=0 a0+a1∗x+a2∗x2+...+an∗xn=0 转化为 ( … ( ( a n x + a n − 1 ) x + a n − 2 ) x + . . . + a 1 ) x + a 0 = 0 (…((a_nx+a_{n-1})x+a_{n-2})x+...+a_1)x+a_0=0 (…((anx+an−1)x+an−2)x+...+a1)x+a0=0 我们只需要枚举 1 1 1 到 m m m 中的每一个答案,然后代入方程式判断即可。 (注:别忘了开 l o n g long long l o n g long long)