【2014】多项式方程区间整数解求解

题目描述

已知多项式方程： $$a_0 + a_1x + a_2x^2 + \dots + a_nx^n = 0$$ 求这个方程在$[1, m]$内的整数解（$n$和$m$均为正整数）。

输入描述

输入共 $n+2$ 行：

1. 第一行包含2个整数 $n$、$m$，每两个整数之间用一个空格隔开。
2. 接下来的 $n+1$ 行每行包含一个整数，依次为 $a_0, a_1, a_2, \dots, a_n$。

输出描述

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

输入样例1

2 10 
1
-2
1

输出样例1

1
1

样例1解释

方程为$1 - 2x + x^2 = 0$，即$(x-1)^2=0$，在$[1,10]$内的整数解为1。

输入样例2

2 10
2
-3
1

输出样例2

2
1
2

样例2解释

方程为$2 - 3x + x^2 = 0$，解为1和2，均在$[1,10]$范围内。

输入样例3

2 10
1
3
2

输出样例3

0

样例3解释

方程为$1 + 3x + 2x^2 = 0$，正整数范围内无满足条件的解。

数据说明

• 对于30%的数据，$0 < n \leq 2$，$|a_i| \leq 100$，$a_n \neq 0$，$m \leq 100$；
• 对于50%的数据，$0 < n \leq 100$，$|a_i| \leq 10^{100}$，$a_n \neq 0$，$m \leq 100$；
• 对于70%的数据，$0 < n \leq 100$，$|a_i| \leq 10^{100000}$，$a_n \neq 0$，$m \leq 10000$；
• 对于100%的数据，$0 < n \leq 100$，$|a_i| \leq 10^{100000}$，$a_n \neq 0$，$m \leq 1000000$。