[NOIP2014] 解方程 题解

题目传送门 题目描述 已知多项式方程： $$a0+a1\ast x+a2\ast x^2+\cdots +an\ast x^n=0$$ 求这个方程在 $[1,m]$ 内的整数解（$n$ 和 $m$ 均为正整数）。 输入格式 输入共 $n+2$ 行。 第一行包含 $2$ 个整数 $n,m$，每两个整数之间用一个空格隔开。 接下来的 n+1n+1 行每行包含一个整数，依次为 $a0,a1,a2\dots 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

说明/提示 题目解析 秦九韶算法结论：对于一个n次多项式，至多做n次乘法和n次加法。 不会秦九韶算法？点这里 不难发现，我们只要枚举区间 $[1,m]$ 之间的整数，带入多项式， $\Theta (n)$ 求出多项式的值，如果与 $0$ 相等就算一个整数解。算法复杂度 $\Theta (nm)$ 。 但是我们看： $|a_i|\le 10^{10000}$ 显然不能直接算，我们只需要模一个大质数就可以了，但是不能有数被整除，这样就不会爆int了，经过检验，$222222227$ （8个2，1个7）就是一个很好的大质数。 代码：

#include<cstdio> #define maxn 1039 #define MOD 222222227//8217 using namespace std; typedef long long ll; typedef long long Type; inline Type read(){ Type sum=0; int flag=0; char c=getchar(); while((c<'0'||c>'9')&&c!='-') c=getchar(); if(c=='-') c=getchar(),flag=1; while('0'<=c&&c<='9'){ sum=(sum<<1)+(sum<<3)+(c^48); sum%=MOD; c=getchar(); } if(flag) return -sum; return sum; } int n,m; ll a[maxn],ans[maxn]; int cnt; int check(int x){ ll res=1; ll ans=0; for(int i=0;i<=n;i++){ ans+=res*a[i]; ans%=MOD; res=res*x%MOD; } if(ans%MOD==0) return 1; return 0; } int main(){ scanf("%d%d",&n,&m); for(int i=0;i<=n;i++) a[i]=read(); int cnt=0; for(int i=1;i<=m;i++) if(check(i)){ ans[++cnt]=i; } printf("%d\n",cnt); for(int i=1;i<=cnt;i++) printf("%d\n",ans[i]); return 0; }