题目描述

已知多项式方程：

a0+a1x+a2x2+⋯+anxn=0a_0+a_1x+a_2x^2+\cdots+a_nx^n=0a0​+a1​x+a2​x2+⋯+an​xn=0

求这个方程在 [1,m][1,m][1,m] 内的整数解（nnn 和 mmm 均为正整数）。

输入输出格式

输入格式：

输入共 n+2n + 2n+2 行。

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

接下来的 n+1n+1n+1 行每行包含一个整数，依次为 a0,a1,a2…ana_0,a_1,a_2\ldots a_na0​,a1​,a2​…an​ 。

输出格式：

第一行输出方程在 [1,m][1,m][1,m] 内的整数解的个数。

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

输入输出样例

输入样例#1： 复制 
2 10 
1
-2
1
输出样例#1： 复制 
1
1
输入样例#2： 复制 
2 10
2
-3
1
输出样例#2： 复制 
2
1
2
输入样例#3： 复制 
2 10
1
3
2
输出样例#3： 复制 
0

说明

对于 30%30\%30% 的数据：0<n≤2,∣ai∣≤100,an≠0,m<1000<n\le 2,|a_i|\le 100,a_n≠0,m<1000<n≤2,∣ai​∣≤100,an​≠0,m<100 。

对于 50%50\%50% 的数据：0<n≤100,∣ai∣≤10100,an≠0,m<1000<n\le 100,|a_i|\le 10^{100},a_n≠0,m<1000<n≤100,∣ai​∣≤10100,an​≠0,m<100 。

对于 70%70\%70% 的数据：0<n≤100,∣ai∣≤1010000,an≠0,m<1040<n\le 100,|a_i|\le 10^{10000},a_n≠0,m<10^40<n≤100,∣ai​∣≤1010000,an​≠0,m<104 。

对于 100%100\%100% 的数据：0<n≤100,∣ai∣≤1010000,an≠0,m<1060<n\le 100,|a_i|\le 10^{10000},a_n≠0,m<10^60<n≤100,∣ai​∣≤1010000,an​≠0,m<106 。

<mark> <mstyle mathcolor="yellow"> <mtext> 臭不要脸的偷了luogu的题面qwq </mtext> </mstyle> \color{yellow}\text{臭不要脸的偷了luogu的题面qwq} 臭不要脸的偷了luogu的题面qwq</mark>

首先,我们想一个暴力
看样子 a i a_i ai​<=100的还比较好拿 <mark> <mstyle mathcolor="yellow"> 废 话 ! </mstyle> \color{yellow}废话! 废话!</mark>

然后呢?剩下的呢?
好像当 a i a_i ai​全都是>0的数的时候,肯定无解是一种,
但是有几分呢?

这里就用到了一个神奇的东西叫做秦九韶算法
不过其实这玩意自己随便搞搞就行了
已知f(x)
f ( x ) = a 0 + a 1 ∗ x + a 2 ∗ x 2 + a 3 ∗ x 3 + a 4 ∗ x 4 + a 5 ∗ x 5 + … … + a n ∗ x n f(x) = a_0 + a_1*x + a_2*x^2+a_3*x^3+a_4*x^4+a_5*x^5+……+a_n*x^n f(x)=a0​+a1​∗x+a2​∗x2+a3​∗x3+a4​∗x4+a5​∗x5+……+an​∗xn
方便起见,我们不妨先让n==5
比如这张图

比较好理解啊~~
稍微解释一下就是:
这里我们就用n==5来举栗子
f ( x ) = a 0 + a 1 ∗ x + a 2 ∗ x 2 + a 3 ∗ x 3 + a 4 ∗ x 4 + a 5 ∗ x 5 f(x) = a_0 + a_1*x + a_2*x^2 + a_3*x^3 + a_4*x^4+a_5*x^5 f(x)=a0​+a1​∗x+a2​∗x2+a3​∗x3+a4​∗x4+a5​∗x5
= a 0 + ( a 1 + a 2 ∗ x + a 3 ∗ x 2 + a 4 ∗ x 3 + a 5 ∗ x 4 ) ∗ x =a_0+(a_1+a_2*x+a_3*x^2+a_4*x^3+a_5*x^4)*x =a0​+(a1​+a2​∗x+a3​∗x2+a4​∗x3+a5​∗x4)∗x
= a 0 + ( a 1 + ( a 2 + a 3 ∗ x + a 4 ∗ x 2 + a 5 ∗ x 3 ) ∗ x ) ∗ x =a_0+(a_1+(a_2+a_3*x+a_4*x^2+a_5*x^3)*x)*x =a0​+(a1​+(a2​+a3​∗x+a4​∗x2+a5​∗x3)∗x)∗x
= a 0 + ( a 1 + ( a 2 + ( a 3 + a 4 ∗ x + a 5 ∗ x 2 ) ∗ x ) ∗ x ) ∗ x ) ∗ x =a_0+(a_1+(a_2+(a_3+a_4*x+a_5*x^2)*x)*x)*x)*x =a0​+(a1​+(a2​+(a3​+a4​∗x+a5​∗x2)∗x)∗x)∗x)∗x
= a 0 + ( a 1 + ( a 2 + ( a 3 + ( a 4 + a 5 ∗ x ) ∗ x ) ∗ x ) ∗ x ) ∗ x =a_0+(a_1+(a_2+(a_3+(a_4+a_5*x)*x)*x)*x)*x =a0​+(a1​+(a2​+(a3​+(a4​+a5​∗x)∗x)∗x)∗x)∗x

return 0 ;

各项式求和的代码实现就是

for(int i = n ; i >= 1 ; i --) {
	sum += (sum+a[i])*x ;
}
sum += a[0] ;

<mark> <mstyle mathcolor="yellow"> 代 码 是 现 敲 的 , 不 知 道 对 不 对 </mstyle> \color{yellow}代码是现敲的,不知道对不对 代码是现敲的,不知道对不对</mark>


```#include <iostream>
#include <stdio.h>
#include <string.h>
#include <algorithm>
#define maxn 1100
#define mod 1000000007
#define int long long 
using namespace std ;
int read () {
	int x = 0 , f = 1 ; char s = getchar() ;
	while(s > '9' || s < '0') {if(s == '-') f = -1 ; s = getchar() ;}
	while(s <='9' && s >='0') {x = (x * 10 + (s-'0'))%mod; s = getchar() ;}
	return x*f ;
}
int n , m , ans , cnt[maxn] , tot ,a[maxn] ;
int check(int x) {
	int sum = 0 ;
	for(int i = n ; i >= 1 ; i --) {
		sum = (sum*x + a[i]*x)%mod ;
	}
	sum = (sum+a[0])%mod ;
	if(sum == 0) return 1 ;
	else return 0 ;
}
signed main () {
	n = read() , m = read() ;
	for(int i = 0 ; i <= n ; i ++) {
		a[i] = read() ;
	}
	for(int i = 1 ; i <= m ; i ++) {
		if(check(i)) {
			tot ++ ;
			cnt[tot] = i ;
		}
	}
	printf("%d\n",tot) ;
	for(int i = 1 ; i <= tot ; i ++) {
		printf("%d\n",cnt[i]) ;
	}
	return 0 ;
}