P2312[秦九韶+读入取模+哈希解方程]

首先讲秦九韶

\[a_0+a_1x+a_2x^2+...+a_nx^n=0\quad\Rightarrow\quad x(x(x(xa_4+a_3)+a_2)+a_1)+a_0=0 \quad[这里以n=4为例] \]

其次，读入取模要改快读板子，改的地方我注释出来了，因为取一次模不放心于是多次取模

#include<bits/stdc++.h>
using namespace std;
/*秦九韶+模大素数来哈希*/
const int maxn=1e6+100;
typedef long long ll;
ll a[4][maxn],n,m;
const int mod1=76543;
const int mod2=23456789;
const int mod3=1e9+9;
namespace IO {
#define gc getchar()
#define pc(x) putchar(x)
    template<typename T>inline void read(T &x1,T &x2,T&x3) {///
        x1=x2=x3=0;//
        int f=1;
        char ch=gc;
        while(ch>'9'||ch<'0') {
            if(ch=='-')f=-1;
            ch=gc;
        }
        while(ch>='0'&&ch<='9')
        {
            x1=(x1<<3)+(x1<<1)+ch-'0',x1%=mod1;//
            x2=(x2<<3)+(x2<<1)+ch-'0',x2%=mod2;//
            x3=(x3<<3)+(x3<<1)+ch-'0',x3%=mod3;//
            ch=gc;
        }
        x1*=f,x2*=f,x3*=f;//
        return;
    }
    template<typename T>inline void write(T x=0) {
        T wr[51];
        wr[0]=0;
        if(x<0)pc('-'),x=-x;
        if(!x)pc(48);
        while(x)wr[++wr[0]]=x%10,x/=10;
        while(wr[0])pc(48+wr[wr[0]--]);
        return;
    }
}
using IO::read;
using IO::write;
bool calc(ll x){
    ll ans1=a[1][n]%mod1,ans2=a[2][n]%mod2,ans3=a[3][n]%mod3;
    for(int i=n-1;i>=0;i--){
        ans1=(ans1*x+a[1][i])%mod1;
        ans2=(ans2*x+a[2][i])%mod2;
        ans3=(ans3*x+a[3][i])%mod3;
    }
    return ans1==0&&ans2==0&&ans3==0;
}
int ans[maxn],num=0;
int main(){
   scanf("%lld%lld",&n,&m);
   for(int i=0;i<=n;i++)
       read(a[1][i],a[2][i],a[3][i]);
    for(int i=1;i<=m;i++){
        if(calc(i)) ans[++num]=i;
    }
    printf("%d\n",num);
    for(int i=1;i<=num;i++){
        printf("%d\n",ans[i]);
    }
}