题目链接
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; }