思路与算法

把系数读成带符号、10^9进制的大整数。选取p>m的素数，且首项系数a_n模p非零；若随机候选整除首项，重选。这样模p的多项式仍是非零的n次多项式。先求它在0到n的值，再建立前向差分。利用有限差分表逐次加法得到1到m的模值，只把模值为0的整数作为候选。由于这些整数在模p下互异，候选最多n个。对每个候选，再用原始大整数系数执行完全精确的Horner运算，只有结果严格为0才输出。

正确性说明

若原多项式在整数x为0，模任意p也为0，因此筛选不可能漏根。首项非零使模多项式次数保持n，域上的根数定理保证模p最多n个根；p>m保证区间内不同整数不是同一剩余类。有限差分是多项式逐点求值的恒等变换，最高阶差分恒定，按从低阶到高阶更新正好由x推进到x+1。模筛允许假阳性，但之后的大整数Horner是精确恒等式，故不会把模碰撞当成真正根。最后按递增x输出得到恰好全部区间整数根。随机选素数只影响耗时，不影响任何一次输出的正确性。

复杂度

设D为系数最大十进制位数、R为模筛候选数（R≤n）。输入及余数初始化O(nD)，差分初始化O(n²)，扫描O(nm)。精确核验O(Rn(D+n log m))个数位操作，含大整数逐位加、减和乘以低精度x；空间O(nD+n+m的输出大小)。选素数额外付出期望常数次首项模运算及试除成本；系数可达100001位，不能先截断为机器整数。

易错点

不能用一个固定模数直接把模值0当答案，也不能在所有系数模p为0时继续筛。非零首项条件必须实际检查。负系数取模要规范化到[0,p)。重根只输出一次，根0、负根和大于m的根都不输出。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
struct Big {
    static const int B = 1000000000;
    vector<int> a;
    int s = 0;
    Big() {
    }
    Big(string t) {
        int st = t[0] == '-' || t[0] == '+';
        s = t[0] == '-' ? -1 : 1;
        for (int i = (int)t.size(); i > st; i -= 9)
            a.push_back(stoi(t.substr(max(st, i - 9), i - max(st, i - 9))));
        trim();
    }
    void trim() {
        while (!a.empty() && !a.back())
            a.pop_back();
        if (a.empty())
            s = 0;
    }
    void times(int x) {
        if (!x) {
            a.clear();
            s = 0;
            return;
        }
        long long c = 0;
        for (auto &v : a) {
            long long t = 1LL * v * x + c;
            v = t % B;
            c = t / B;
        }
        while (c) {
            a.push_back(c % B);
            c /= B;
        }
    }
    void add(const Big &b) {
        if (!b.s)
            return;
        if (!s) {
            *this = b;
            return;
        }
        if (s == b.s) {
            a.resize(max(a.size(), b.a.size()), 0);
            long long c = 0;
            for (size_t i = 0; i < a.size(); i++) {
                long long t = (long long)a[i] + (i < b.a.size() ? b.a[i] : 0) + c;
                a[i] = t % B;
                c = t / B;
            }
            if (c)
                a.push_back(c);
            return;
        }
        int cmp = a.size() != b.a.size() ? (a.size() > b.a.size() ? 1 : -1) : 0;
        if (!cmp)
            for (int i = (int)a.size() - 1; i >= 0; i--)
                if (a[i] != b.a[i]) {
                    cmp = a[i] > b.a[i] ? 1 : -1;
                    break;
                }
        if (!cmp) {
            a.clear();
            s = 0;
            return;
        }
        if (cmp < 0) {
            Big t = b;
            t.add(*this);
            *this = move(t);
            return;
        }
        int c = 0;
        for (size_t i = 0; i < a.size(); i++) {
            long long v = (long long)a[i] - (i < b.a.size() ? b.a[i] : 0) - c;
            c = v < 0;
            if (c)
                v += B;
            a[i] = v;
        }
        trim();
    }
    int mod(int p) const {
        long long v = 0;
        for (int i = (int)a.size() - 1; i >= 0; i--)
            v = (v * B + a[i]) % p;
        return s < 0 && v ? p - v : v;
    }
};
bool prime(int x) {
    if (x < 2)
        return false;
    for (int i = 2; 1LL * i * i <= x; i++)
        if (x % i == 0)
            return false;
    return true;
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    if (!(cin >> n >> m))
        return 0;
    vector<Big> a;
    for (int i = 0; i <= n; i++) {
        string s;
        cin >> s;
        a.emplace_back(s);
    }
    mt19937 rng((unsigned)chrono::steady_clock::now().time_since_epoch().count());
    int p;
    do {
        p = 1000003 + (rng() % 1000000);
        while (!prime(p))
            p++;
    } while (a[n].mod(p) == 0);
    vector<int> c(n + 1), v(n + 1), delta(n + 1);
    for (int i = 0; i <= n; i++)
        c[i] = a[i].mod(p);
    for (int x = 0; x <= n; x++) {
        long long f = 0;
        for (int j = n; j >= 0; j--)
            f = (f * x + c[j]) % p;
        v[x] = f;
    }
    for (int j = 0; j <= n; j++) {
        delta[j] = v[0];
        for (int i = 0; i < n - j; i++) {
            v[i] = v[i + 1] - v[i];
            if (v[i] < 0)
                v[i] += p;
        }
    }
    vector<int> ans;
    for (int x = 1; x <= m; x++) {
        for (int j = 0; j < n; j++) {
            delta[j] += delta[j + 1];
            if (delta[j] >= p)
                delta[j] -= p;
        }
        if (delta[0])
            continue;
        Big f;
        for (int j = n; j >= 0; j--) {
            f.times(x);
            f.add(a[j]);
        }
        if (!f.s)
            ans.push_back(x);
    }
    cout << ans.size() << '\n';
    for (int x : ans)
        cout << x << '\n';
}