题意描述
洛谷链接
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;
}
|