[FROM LUOGU]解方程

传送门

SOL 首先有很大的数据规模，所以只能取模判断是否为0 其次计算这个多项式的值可能比较复杂，如果用pow函数或者快速幂复杂度就肯定炸了，常数小的话可以过70分 所以可以迭代： $$计算第一次：an\ast x+an-1$$ $$计算第二次：(an\ast x+an-1)\ast x+an-2$$ $$\dots \dots$$ 如此以来，求一个多项式就只需计算$n$次 除此之外，可以进行一些剪枝，例如对于一个小质数$p$，先求$1<=x<p$的答案，然后对于$x<=p<=m$，看一下$xmodp$即可 为了保险起见，最好多用几个质数（就像Hash一样），如果取模出来的答案都为$0$，才确定为解，这样同时也可以减去一些无用状态

代码：

#include<bits/stdc++.h> using namespace std; #define re register #define ll long long inline char nc(){ static char buf[10000],*p1=buf,*p2=buf; return p1==p2&&(p2=(p1=buf)+fread(buf,1,10000,stdin),p1==p2)?EOF:*p1++; } inline int rd(){ int re data=0;static char ch=0;ch=nc(); while(!isdigit(ch))ch=nc(); while(isdigit(ch))data=(data<<1)+(data<<3)+(ch^48),ch=nc(); return data; } const int N=1e6+5,pa=1e5+7,pb=1e9+7; int n,m,a[105],b[N],ans[N],cnt;char ch;bool w,tag[pa];ll aa,bb; inline int f(ll x,int mod,int *t,ll sum=0){sum=t[n];for(int re i=n-1;~i;--i)sum=(sum*x+t[i])%mod;return sum;} signed main(){ n=rd(),m=rd(); for(int re i=0;i<=n;++i){ aa=bb=0,w=0,ch=nc(); while(!isdigit(ch)&&ch!='-')ch=nc(); if(ch=='-')w=1,ch=nc(); while(isdigit(ch))aa=((aa<<1)+(aa<<3)+(ch^48))%pa,bb=((bb<<1)+(bb<<3)+(ch^48))%pb,ch=nc(); a[i]=w?pa-aa:aa,b[i]=w?pb-bb:bb; } for(int re i=0;i^pa;++i)if(!f(i,pa,a))tag[i]=1; for(int re i=1;i<=m;++i){ if(!tag[i%pa])continue; if(!f(i,pb,b))ans[++cnt]=i; }printf("%d\n",cnt); for(int re i=1;i<=cnt;++i)printf("%d\n",ans[i]); exit(0); }