题目描述

已知多项式方程：

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]$ 内的整数解（$n$ 和 $m$ 均为正整数）。

输入输出格式

输入格式：

输入共 $n+2$ 行。

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

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

输出格式：

第一行输出方程在 $[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\%$ 的数据：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\%$ 的数据：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\%$ 的数据：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\%$ 的数据：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 。

---

$\text{臭不要脸的偷了luogu的题面qwq}$

---

首先,我们想一个暴力 看样子$a_i$<=100的还比较好拿 $废话!$

---

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

---

这里就用到了一个神奇的东西叫做秦九韶算法 不过其实这玩意自己随便搞搞就行了 已知f(x) $$f(x)=a_0+a_1\ast x+a_2\ast x^2+a_3\ast x^3+a_4\ast x^4+a_5\ast x^5+\dots \dots +a_n\ast x^n$$ 方便起见,我们不妨先让n==5 比如这张图

比较好理解啊~~ 稍微解释一下就是: 这里我们就用n==5来举栗子 $$f(x)=a_0+a_1\ast x+a_2\ast x^2+a_3\ast x^3+a_4\ast x^4+a_5\ast x^5$$ $$=a_0+(a_1+a_2\ast x+a_3\ast x^2+a_4\ast x^3+a_5\ast x^4)\ast x$$ $$=a_0+(a_1+(a_2+a_3\ast x+a_4\ast x^2+a_5\ast x^3)\ast x)\ast x$$ $$=a_0+(a_1+(a_2+(a_3+a_4\ast x+a_5\ast x^2)\ast x)\ast x)\ast x)\ast x$$ $$=a_0+(a_1+(a_2+(a_3+(a_4+a_5\ast x)\ast x)\ast x)\ast x)\ast x$$

return 0 ;

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

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

$代码是现敲的,不知道对不对$

---

```#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 ; }