题目大意

给定 $a_0,a_1,\cdots,a_n$，求 $a_0+a_1x+a_2x^2+\cdots+a_nx^n=0$ 在 $[1,m]$ 范围内的解，数据范围 $|a_i|\le 10^{10000}$。

解题思路

注意到这个方程是秦九韶公式的模板（秦九韶公式可专门解决这类问题），过程如下：

$$\begin{aligned}a_0+a_1x+a_2x^2+\cdots+a_nx^n&=0\\a_0+x(a_1+a_2x+a_3x^2+\cdots+a_nx^{n-1})&=0\\a_0+x\left(a_1+x(a_2+a_3x+a_4x^2\cdots+a_nx^{n-2})\right)&=0\\\cdots\\a_0+x\left(a_1+x\left(\cdots(a_{n-1}+a_nx)\right)\right)&=0\end{aligned}$$

这时只需要设 $f_1=a_{n-1}+a_nx$，即可得到 $f_i=f_{i-1}x+a_{n-i}$，最后 $f_n$ 即为结果，这样可拿 $50$ 分。因为数据范围中有个很恶心的 $10^{10000}$，高精度太麻烦，于是考虑哈希（因为我们并不关心 $f_n$ 到底是什么数，只关心它是不是 $0$），读入和计算 $f_i$ 的时候都模上一个大质数（最好是 $10^9+7$）即可（读入时的模可用快读）。

AC 代码

#include <bits/stdc++.h>
#define ll long long
#define endl putchar(10)
#define spc putchar(32)
#define R register
using namespace std;
#ifndef ONLINE_JUDGE
#define debug(x) cerr << #x << " = " << x, endl
#endif

const ll mod=1e9+7;

inline ll read()
{
    ll x=0,f=1; char c=getchar();

    while(c<48 || c>57)
    {
        if(c=='-') f=-1;
        c=getchar();
    }

    while(c>47 && c<58)
    x=((x<<1)+(x<<3)+c-48)%mod, c=getchar();
    return x*f;
}

inline void write(ll x)
{
    static ll sta[41]; ll top=0;
    if(x<0) putchar('-'), x=-x;
    do sta[top++]=x%10, x/=10; while(x);
    while(top) putchar(sta[--top]+48);
}

ll n,m,a[101],f[101],ans[1000001],cnt;

int main()
{
    n=read(); m=read();
    for(R int i=0; i<=n; ++i) a[i]=read();

    for(R int i=1; i<=m; ++i)
    {
        f[1]=(a[n]*i+a[n-1])%mod;
        for(R int j=2; j<=n; ++j) f[j]=(f[j-1]*i+a[n-j])%mod;
        if(!f[n]) ans[++cnt]=i;
    }

    write(cnt); endl;
    for(int i=1; i<=cnt; ++i) write(ans[i]), endl;
    return 0;
}