luogu2312 [NOIp2015]解方程 (秦九韶)

秦九韶算法：多项式$a_0+a_1x+a_2x^2+...+a_nx^n=a_0+x(a_1+x(a_2+...+(xa_n))..)$，这样对于一个x，可以在O(n)求出结果

为了避免高精度，我们同时模几个质数来判断每个的值是不是等于0，这样出锅的概率就非常小

然而这样做复杂度是O(nm)，过不去

我们发现对于某一个模数p，x+kp和x算出来的结果模p以后是一样的，这样的话，只要先算出来一个比较小的p以内的所有结果，再去从那些里挑出模p等于0的，再去判断这些+kp以后模别的等不等于0，这样复杂度就会减小很多

我选择了13331,19260817和1e9+7

另外快读也需要修改一下

 #include<bits/stdc++.h>

 #define pa pair<int,int>

 #define CLR(a,x) memset(a,x,sizeof(a))

 using namespace std;

 typedef long long ll;

 const int maxn=,maxm=1e6+;

 const int p[]={,,1e9+};

 inline void rd(int &x1,int &x2,int &x3){

     x1=x2=x3=;char c=getchar();int neg=;

     while(c<''||c>''){if(c=='-') neg=-;c=getchar();}

     while(c>=''&&c<=''){

         x1=(x1*+c-'')%p[];

         x2=(x2*+c-'')%p[];

         x3=(x3*10ll+c-'')%p[];

         c=getchar();

     }x1=x1*neg%p[];

     x2=x2*neg%p[];

     x3=x3*neg%p[];

 }

 int N,M,a[maxn][],cnt;

 queue<int> q;

 bool ans[maxm];

 bool judge(int id,int x){

     int sum=a[N][id];x%=p[id];

     for(int i=N;i;i--) sum=((ll)sum*x+a[i-][id])%p[id];

     return sum==;

 }

 int main(){

     // freopen("testdata.in","r",stdin);

     int i,j,k;

     scanf("%d%d",&N,&M);

     for(i=;i<=N;i++) rd(a[i][],a[i][],a[i][]);

     for(i=;i<=min(M,p[]);i++){

         if(judge(,i)) q.push(i%p[]);

     }

     while(!q.empty()){

         int x=q.front();q.pop();

         for(int i=;x+p[]*i<=M;i++){

             if(judge(,x+p[]*i)&&judge(,x+p[]*i)) ans[x+p[]*i]=,cnt++;

         }

     }

     printf("%d\n",cnt);

     for(i=;i<=M;i++) if(ans[i]) printf("%d\n",i);

     return ;

 }