「NOIP2014」解方程 - 数论 + Hash

发表于 更新于 分类于 ， 阅读次数：

题意描述

洛谷链接

LibreOJ 链接

已知多项式方程：

\[a_0+a_1x+a_2x^2+\cdots+a_nx^n=0\]

求这个方程在 \([1,m]\) 内的整数解（\(n\) 和 \(m\) 均为正整数）。

解题思路

这道题数据范围过大，显然我们无法用正常思路解决。而 \(m\) 的数据范围不大，于是我们可以尝试枚举 \(x\) 来得出答案。

通过同余性质我们可以知道，对于一个数 \(p\)，如果 \(\sum_{i = 0}^n{a_ix^i} = 0\)，则 \(\sum_{i = 0}^n{a_ix^i} \equiv 0 \pmod p\)。于是我们可以用 Hash 的思想解决这道题。

我们可以将 \(a_ix^i \bmod p\) 存储累加，然后最后于 0 比较即可。如果担心被卡可以使用多模数 Hash（虽然这道题经过测试只需要 \(998244353\) 这个模数可过）。

这道题可以用秦九昭公式进一步优化，但 whk 数学还没学到那就没写了 QWQ

代码演示

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
#include <cstdio>
#include <iostream>
#include <vector>

const int MAXN = 100;
const int MOD = 998244353;

inline long long read() {
    long long x = 0, w = 1;
    char ch = 0;
    while (ch < '0' || ch > '9') {
        if (ch == '-') w = -1;
        ch = getchar();
    }
    while (ch >= '0' && ch <= '9') {
        x = (x * 10 + (ch - '0')) % MOD;
        ch = getchar();
    }
    return x * w;
}

int main() {
    int n, m;
    static long long a[MAXN + 1];

    scanf("%d %d", &n, &m);
    for (int i = 0; i <= n; i++) a[i] = read();

    static std::vector<int> ans;
    for (int i = 1; i <= m; i++) {
        long long res = 0, p = 1;
        for (int j = 0; j <= n; j++) {
            res = (res + (a[j] * p) % MOD) % MOD;
            p = (p * i) % MOD;
        }

        if (res == 0) ans.push_back(i);
    }

    printf("%zu\n", ans.size());
    for (int each : ans) printf("%d\n", each);

    return 0;
}