[NOIP2014]解方程

形式化题目

给定 $n + 1$ 个整系数 $a_0, a_1, \ldots, a_n$ ，以及正整数 $m$ 。求所有满足

f(x) = a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n = 0

的整数 $x \in [1, m]$ ，按从小到大输出。系数与 $m$ 都可能极大——本题真实数据中 $n \leqslant 100$ 、 $m \leqslant 10^6$ ，单个系数的十进制位数可达上万。

样例： $f(x) = 1 - 2x + x^2 = (x-1)^2$ ，在 $[1, 10]$ 内只有 $x = 1$ 使 $f(x) = 0$ ，答案为 $1$ 个根： $1$ 。

正解

思路

朴素做法与它的瓶颈。 最直接的想法是：枚举 $x = 1 \ldots m$ ，把 $f(x)$ 精确算出来看是不是 $0$ 。问题出在"精确算"上：本题系数可达 $10^{10000}$ 量级， $x$ 可达 $10^6$ ，一个点的精确值有上万位数字，即使每一步乘加都摊 $O(1)$ 的位数分析也是骗人的——单次精确求值本身就是上万位整数的连乘， $10^6$ 个点乘下来根本算不完。 $n$ 和 $m$ 的规模逼我们放弃"精确求值"这个动作本身。

核心观察：只判"是不是 0"，可以在模意义下判。 设一个素数 $p$ ，若整数 $f(x) = 0$ ，那么

f(x) \bmod p = 0

必然成立（ $0$ 模任何数都是 $0$ ）。反过来， $f(x) \bmod p = 0$ 时 $f(x)$ 未必真的是 $0$ ——非根可能"撞"成模意义下的假根。于是可以在模 $p$ 的世界里做整套判定：把系数先归约到 $[0, p)$ ，对每个 $x$ 用秦九韶算法（Horner 法则）求 $f(x) \bmod p$ ，全程只做机器字范围内的乘法与取模，单点代价从"上万位大数连乘"降到 $O(n)$ 次小整数运算，总代价 $O(nm)$ 。

秦九韶算法本身也是本题的正式考点。对 $f(x) = a_0 + a_1 x + a_2 x^2$ ，逐项计算 $x^2$ 再乘系数要做多次乘法；而把它改写成嵌套形式：

f(x) = a_0 + x\,(a_1 + x\,a_2)

求值就变成"从最高次系数开始，反复做乘 $x$ 、加下一项"—— $n$ 次乘法、 $n$ 次加法，没有任何幂运算。以 $n = 2$ 的样例 $f(x) = 1 - 2x + x^2$ 、 $x = 3$ 为例，模 $p = 7$ 的推演如下：

步骤	读到的系数	$v \gets v \cdot x + c$	结果（ $\bmod\ 7$ ）
初始	—	$v = 0$	0
1	$a_2 = 1$	$0 \cdot 3 + 1$	1
2	$a_1 = -2$	$1 \cdot 3 + (-2)$	1
3	$a_0 = 1$	$1 \cdot 3 + 1$	4

模 $7$ 意义下 $f(3) = 4 \neq 0$ ，准确反映 $f(3) = 4$ 不是根；而 $x = 1$ 时同样的三步会得到 $v = 0$ ，被收进候选集。表格里最值得看的是**"读到的系数"一列是倒着走的**（ $a_2 \to a_1 \to a_0$ ），这正是 Horner 法则与逐项求值最大的实现差异；另一列 $v$ 每步都缩在 $[0, p)$ 内，这就是"全程小整数"的直观含义。

筛子必须配复验。 模 $p$ 判定是单向的：真根一定通过，假根也可能通过。若只输出模意义下的根，一个精心构造的非根（例如 $f(x) = p \cdot g(x)$ ，处处 $f(x) \bmod p = 0$ 但 $f(x)$ 处处非零）就能骗过筛子。所以把幸存者再交还给精确复验：候选根至多 $O(n)$ 个（模 $p$ 的意义下， $f(x) \bmod p$ 作为 $x$ 的 $n$ 次多项式在模域里至多 $n$ 个根），每个候选做一次上万位整数的精确 Horner，代价可以忽略。两段组合起来：筛掉 $10^6$ 个点里 $99.9999\%$ 的非根，剩下的用大整数逐一确认——期望零误判，最坏也只在"大量真根 + 伪装非根"时退化，真根本来就至多 $n$ 个，复验总量始终有界。

C++ 里没有大整数，"筛 + 双模数复验"就是终态；Python 天生有任意精度整数，复验反而成了免费的正确性保险。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-10-10 11:30
 * update_at: 2026-10-10 11:30
 */

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int BASE = 1000000000;
struct BigInt {
    vector<int> d;
    int sign;
    BigInt(ll x = 0) { sign = 1; if (x < 0) { sign = -1; x = -x; } if (x == 0) sign = 0; while (x) { d.push_back(x % BASE); x /= BASE; } }
};
void trim(BigInt &a) { while (!a.d.empty() && a.d.back() == 0) a.d.pop_back(); if (a.d.empty()) a.sign = 0; }
BigInt read_big(string s) { BigInt a; a.d.clear(); a.sign = 1; int pos = 0; if (s[0] == '-') { a.sign = -1; pos = 1; } for (int i = s.size(); i > pos; i -= 9) { int l = max(pos, i - 9); int x = 0; for (int j = l; j < i; j++) x = x * 10 + s[j] - '0'; a.d.push_back(x); } trim(a); return a; }
int cmp_abs(const BigInt &a, const BigInt &b) { if (a.d.size() != b.d.size()) return a.d.size() < b.d.size() ? -1 : 1; for (int i = (int)a.d.size() - 1; i >= 0; i--) if (a.d[i] != b.d[i]) return a.d[i] < b.d[i] ? -1 : 1; return 0; }
BigInt add_abs(const BigInt &a, const BigInt &b) { BigInt c; c.sign = 1; int n = max(a.d.size(), b.d.size()); c.d.assign(n, 0); ll carry = 0; for (int i = 0; i < n; i++) { ll v = carry; if (i < (int)a.d.size()) v += a.d[i]; if (i < (int)b.d.size()) v += b.d[i]; c.d[i] = v % BASE; carry = v / BASE; } if (carry) c.d.push_back(carry); trim(c); return c; }
BigInt sub_abs(const BigInt &a, const BigInt &b) { BigInt c; c.sign = 1; c.d.assign(a.d.size(), 0); ll borrow = 0; for (int i = 0; i < (int)a.d.size(); i++) { ll v = (ll)a.d[i] - borrow - (i < (int)b.d.size() ? b.d[i] : 0); if (v < 0) { v += BASE; borrow = 1; } else borrow = 0; c.d[i] = v; } trim(c); return c; }
BigInt add_big(BigInt a, BigInt b) { if (a.sign == 0) return b; if (b.sign == 0) return a; if (a.sign == b.sign) { BigInt c = add_abs(a, b); c.sign = a.sign; return c; } int cmp = cmp_abs(a, b); if (cmp == 0) return BigInt(0); if (cmp > 0) { BigInt c = sub_abs(a, b); c.sign = a.sign; return c; } BigInt c = sub_abs(b, a); c.sign = b.sign; return c; }
BigInt mul_int(BigInt a, ll m) { if (a.sign == 0 || m == 0) return BigInt(0); if (m < 0) { a.sign = -a.sign; m = -m; } BigInt c; c.sign = a.sign; c.d.assign(a.d.size(), 0); ll carry = 0; for (int i = 0; i < (int)a.d.size(); i++) { __int128 v = (__int128)a.d[i] * m + carry; c.d[i] = (ll)(v % BASE); carry = (ll)(v / BASE); } while (carry) { c.d.push_back(carry % BASE); carry /= BASE; } trim(c); return c; }
BigInt div_int(BigInt a, ll m) { BigInt c; c.sign = a.sign; c.d.assign(a.d.size(), 0); ll rem = 0; for (int i = (int)a.d.size() - 1; i >= 0; i--) { __int128 cur = (__int128)rem * BASE + a.d[i]; c.d[i] = (ll)(cur / m); rem = (ll)(cur % m); } trim(c); return c; }
bool less_big(const BigInt &a, const BigInt &b) { if (a.sign != b.sign) return a.sign < b.sign; if (a.sign == 0) return false; int cmp = cmp_abs(a, b); return a.sign > 0 ? cmp < 0 : cmp > 0; }
bool is_zero(const BigInt &a) { return a.sign == 0; }
ostream& operator<<(ostream &os, const BigInt &a) { if (a.sign == 0) { os << 0; return os; } if (a.sign < 0) os << '-'; int n = a.d.size(); os << a.d[n - 1]; for (int i = n - 2; i >= 0; i--) os << setw(9) << setfill('0') << a.d[i]; return os; }

const ll P=2147483647LL;
ll str_mod(string s){int i=0,neg=0; if(s[0]=='-'){neg=1;i=1;} ll v=0; for(;i<(int)s.size();i++) v=((__int128)v*10+s[i]-'0')%P; if(neg && v) v=P-v; return v;}
ll mod_horner(vector<ll>&rev,ll x){ll v=0; for(int i=0;i<(int)rev.size();i++) v=((__int128)v*x+rev[i])%P; return v;}
BigInt horner(vector<BigInt>&c,int x){BigInt v(0); for(int i=(int)c.size()-1;i>=0;i--) v=add_big(mul_int(v,x), c[i]); return v;}
int main(){ios::sync_with_stdio(false);cin.tie(nullptr); int n,m; if(!(cin>>n>>m)) return 0; vector<BigInt> coeff(n+1); vector<ll> rev(n+1); for(int i=0;i<=n;i++){string s;cin>>s; coeff[i]=read_big(s); rev[n-i]=str_mod(s);} vector<int> roots; for(int x=1;x<=m;x++) if(mod_horner(rev,x)==0 && is_zero(horner(coeff,x))) roots.push_back(x); cout<<roots.size()<<'\n'; for(int i=0;i<(int)roots.size();i++) cout<<roots[i]<<'\n'; return 0;}

python

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49#!/usr/bin/env python3
# Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
# rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
# rainboy的学习导航网站: https://idx.roj.ac.cn
# create_at: 2026-10-02 11:10
# update_at: 2026-10-02 11:17

import sys

sys.set_int_max_str_digits(20000)  # 系数可达上万位十进制，放开 int() 的转换位数限制

P = 2147483647  # 梅森素数 2^31-1：期望假阳性 O(m/p) ≈ 0，幸存者再精确复验


def mod_horner(coeffs_rev_mod: list[int], x: int) -> int:
    """模意义下秦九韶：传入倒序（a_n 在前）的系数，反复乘 x 加下一项，随时取模。"""
    v = 0
    for c in coeffs_rev_mod:
        v = (v * x + c) % P
    return v


def horner(coeffs: list[int], x: int) -> int:
    """大整数精确秦九韶：Python 原生大整数直接算，不怕系数上百位。"""
    v = 0
    for c in reversed(coeffs):
        v = v * x + c
    return v


def solve() -> None:
    it = map(int, sys.stdin.buffer.read().split())
    n, m = next(it), next(it)
    coeffs = [next(it) for _ in range(n + 1)]

    # 第一遍：模 P 筛掉绝大多数非根（C++ 正解的本体就是这一步）。
    # Horner 要从最高次算起：把负系数先归一到 [0, P)，再整体反转成 a_n 在前。
    coeffs_rev_mod = [c % P for c in reversed(coeffs)]
    candidates = [x for x in range(1, m + 1) if mod_horner(coeffs_rev_mod, x) == 0]

    # 第二遍：幸存者用原系数精确复验，保证零误判。
    roots = [x for x in candidates if horner(coeffs, x) == 0]

    print(len(roots))
    print('\n'.join(map(str, roots)))


if __name__ == "__main__":
    solve()

复杂度

时间：模筛 $O(nm)$ 次小整数乘加（ $n \leqslant 100$ 、 $m \leqslant 10^6$ 时约 $10^8$ 次机器运算，正是 C++ 正解的量级）；候选根 $\leqslant n$ 个，精确复验 $O(n^2)$ 次大数位运算，可忽略。Python 常数大，同一算法在官方 1s 限时内可能超时，但复杂度与 C++ 正解同阶。
空间： $O(n)$ 存系数（模意义一份、原值一份），与 $m$ 无关。

总结

本题是 NOIP2014 提高组经典题，考点是秦九韶算法 + 同余判定的组合：数据范围攻击的是"精确求值"，于是把"值是否为 0"这个判定整体搬进模 $p$ 世界，用 Horner 法则把单点求值压成 $n$ 次乘加。三个值得带走的经验：一是 Horner 的实现要点是系数倒序进入循环，v = v * x + c 一行就是嵌套形式的逐层展开；二是"模意义判定 = 单向筛"，真根必中、假根可能漏进来，所以筛子后面必须补一道复验（双模数或这里的大整数精确复验），否则等于把正确性押在数据不卡上；三是 $O(nm)$ 的逐点判定已经封顶——多项式在模域内没有已知的整体"求根公式"能少于逐点检查，这也是本题正解就是暴力加"换域"的全部原因。

图示解析

筛与验的两段流水线

flowchart LR
    A["全部候选 x = 1 … m<br/>(m ≤ 10^6)"] --> B["模 p 秦九韶筛<br/>每点 O(n) 次小整数乘加"]
    B -->|"模值 ≠ 0<br/>绝不是根"| C["直接淘汰 ≈ m 个"]
    B -->|"模值 = 0<br/>幸存者 ≤ n 个"| D["大整数精确复验<br/>原系数 Horner"]
    D -->|"值 ≠ 0"| E["淘汰假根"]
    D -->|"值 = 0"| F["确认真根，按序输出"]

图里体现的是"漏斗"结构：左边的模筛负责把 $10^6$ 量级的候选快速缩到 $n$ 以内，右边的精确复验只对漏斗出口负责。两段各自单调——模筛只可能漏进假根、绝不会错杀真根（因为真根模后必为 $0$ ），复验只可能淘汰、绝不会再放行，所以整条流水线的输出恰好是真根集合。

目录

形式化题目

正解

思路

代码

复杂度

总结

图示解析

筛与验的两段流水线