秦九韶算法
对于式子 \(a_nx^n + a_{n-1}x^{n-1} + \dots + a_1x^1 + a_0\),
可以变形为 \((\dots((a_nx+a_{n-1})x+\dots + a_1)x + a_0\)
做法
枚举 \([1,m]\) 中的所有数作为 \(x\) 带入式子中利用秦九韶算法算出结果,看结果是否为 \(0\) 。
对于系数 \(a_i\) 的输入,可以参照哈希的思想,将其模上一个很大 (至少大于 \(m\))的质数,这里取了\(1000000007\)。
PS: 这种哈希的方法可能会产生哈希冲突,常常有毒瘤出题人会利用这些细节来卡人,这道题的数据比较水,加上本人运气较好,没有产生哈希冲突,经验证:质数 \(10001891\) 会产生哈希冲突,若读者不放心,可以多做几次哈希,减少冲突的可能性。
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N = 105, Mod = 1e9 + 7;
inline LL read()
{
LL x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')
f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
x=((x<<1)+(x<<3)+(ch^48)) % Mod;
ch=getchar();
}
return x*f;
}
LL n,m;
LL cnt = 0;//可行解个数
LL ans[N];
LL a[N];//系数
LL count(LL x)//秦九韶
{
LL res = 0;
for(LL i=n;i>=1;i--) res = ((res + a[i]) * x) % Mod;
res = (res + a[0]) % Mod;
return res;
}
int main()
{
cin>>n>>m;
for(LL i=0;i<=n;i++) a[i] = read();
for(LL i=1;i<=m;i++)
{
if(count(i) == 0)
{
ans[++cnt] = i;
}
}
cout<<cnt<<endl;
for(LL i=1;i<=cnt;i++) cout<<ans[i]<<endl;
return 0;
}