题目链接
https://www.luogu.org/problem/P2312
题解
基本思想是枚举所有解，但如果采用传统的方法计算多项式的值，计算量是无法承受的。
因此，我们需要使用更高效的多项式计算方法——秦九韶算法！
计算一个多项式 \(f(x)=a_nx^n+a_{n-1}x^{n-1}+ \ldots +a_1x+a_0\)，传统的计算方法是这样的：
long long calc(int x)
{
long long ans=a[0],x1=x;
for(int i=1;i<=n;i++)
{
x1=1;
for(int j=1;j<=i;j++)
x1=x1*x%MOD;
ans=ans+a[i]*x1%MOD;
}
return ans;
}
即花费 \(O(n^2)\) 的时间求出所有 \(x^i\) 的值，再分别与系数相乘。采用这么慢的方法计算显然是无法解决问题的。
只需要采用一个小小的优化，就可以仅仅采用 \(n\) 次乘法就求出所有 \(x^i\) 的值：
long long calc(int x)
{
long long ans=a[0],x1=x;
for(int i=1;i<=n;i++)
{
ans=(ans+a[i]*x1)%MOD;
x1=x1*x%MOD;
}
return ans;
}
这种方法利用了之前已经算出来的低次项的值，避免了重复计算，总的乘法次数达到了 \(2n\) 次，加法次数有 \(n\) 次，已经比刚才快了很多，在洛谷的评测机上已经足够通过这道题。
但还有效率最高的秦九韶算法。
我们对多项式 \(f(x)\) 进行如下处理：
$$ \begin{eqnarray} f(x) &=& a_nx^n+a_{n-1}x^{n-1}+ \ldots +a_1x+a_0 \\ &=& (a_nx^{n-1}+a_{n-1}x^{n-2}+ \ldots +a_1)x+a_0 \\ &=& ((a_nx^{n-2}+a_{n-2}x^{n-3}+ \ldots +a_2)x+a_1)x+a_0 \\ &=& \ldots \\ &=& (\ldots((a_nx+a_{n-1})x+a_{n-2})x+ \ldots +a_1)x+a_0 \end{eqnarray}$$
计算时，我们先算出括号最里层的值，再一步步往外算，这样我们就可以只用 \(n\) 次乘法和 \(n\) 次加法，就高效地解决了问题！
在解决本题时，因为高精度的效率实在太低，我们需要对中间结果取模，这个过程中有被精心构造的 hack 数据卡的风险…（不过看出来出题人并没有卡，毕竟高精度实在太慢了…）
#include <cstdio>
#include <iostream>
#include <algorithm>
#define MOD 19260817
using namespace std;
long long a[105];
int res[1000005],cnt,n,m;
long long read()
{
long long num=0,flag=1;
char ch=getchar();
while(ch<'0'||ch>'9')
{
if(ch=='-')flag=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9')
{
num=((num*10)+(ch-'0'))%MOD;
ch=getchar();
}
return flag*num;
}
inline long long calc(int x)
{
long long ans=0;
for(int i=n;i;i--)
ans=(ans+a[i])*x%MOD;
ans=(ans+a[0])%MOD;
return ans;
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=0;i<=n;i++)
a[i]=read();
for(int i=1;i<=m;i++)
if(!calc(i))res[++cnt]=i;
printf("%d\n",cnt);
for(int i=1;i<=cnt;i++)
printf("%d\n",res[i]);
return 0;
}