[NOIP 2014] 解方程

发表于2017-04-09更新于2020-08-06

题目大意

已知多项式方程：

a0+a1x+a2x2+⋯+anxn=0a_0 + a_1 x + a_2 x^2 + \cdots + a_n x^n = 0

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

1⩽n⩽1001 \leqslant n \leqslant 100

∣ai∣⩽1010,000|a_i| \leqslant 10^{10,000}

1⩽m⩽1,000,0001 \leqslant m \leqslant 1,000,000

题目链接

【NOIP 2014】解方程 - LibreOJ 2503

题解

当多项式的值在模 pp 意义下为 00 时，我们便认为它的值为 00，同时，x+kpx + kp 的值也为 00，因此，我们只需计算 [1,  p−1][1, \; p - 1] 内的值。当然，这是错的，我们再选几个模数（质数）进行验证，如果值都为 00，那么就很有可能是解。同时，模意义下的运算避免了高精度。

质数的选取很烦。。。小了会少一些解，多了会 T。。。（BZOJ 挂的时候在 UOJ 上做的，WA 了好几次。。。等 BZOJ 好了后，UOJ 上能 AC 的在 BZOJ 上 TLE 了。。。）

很有趣的题，应该不会再出的题。。。很好奇当时这道题的得分情况。。。

代码

这是 BZOJ 上 AC 的，UOJ 上的质数是 1493914939,，150193，150193，52852375285237。

质数哪来的？瞎写的。。。

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
#include <cstdio>
#include <list>
const int MAXN = 105;
const int MAXM = 1000005;
const int MAXLEN = 10005;
const int PRIME_NUM = 2;
const int MODS[PRIME_NUM] = {21893, 18341629};
int n, m;
int a[MAXN];
char s[MAXN][MAXLEN];
int parseInt(char *s, int mod) {
    int sgn = 1, res = 0;
    if (*s == '-') sgn = -1, s++;
    for (; *s; s++) res = (res * 10 + *s - '0') % mod;
    return res * sgn;
}
int calc(int x, int mod) {
    long long res = 0, pow = 1;
    for (int i = 0; i <= n; i++) {
        res = (res + a[i] * pow) % mod;
        pow = pow * x % mod;
    }
    return (int) res;
}
int main() {
    scanf("%d %d", &n, &m);
    for (int i = 0; i <= n; i++) scanf("%s", s[i]);
    std::list<int> roots;
    int p = MODS[0];
    for (int i = 0; i <= n; i++) a[i] = parseInt(s[i], p);
    for (int i = 1; i < p; i++) {
        int y = calc(i, p);
        if (y == 0) for (int j = i; j <= m; j += p) roots.push_back(j);
    }
    for (int i = 1; i < PRIME_NUM; i++) {
        int p = MODS[i];
        for (int j = 0; j <= n; j++) a[j] = parseInt(s[j], p);
        for (std::list<int>::iterator it = roots.begin(); it != roots.end(); ) {
            int y = calc(*it, p);
            if (y != 0) it = roots.erase(it);
            else it++;
        }
    }
    roots.sort();
    printf("%lu\n", roots.size());
    for (std::list<int>::iterator it = roots.begin(); it != roots.end(); it++) 
        printf("%d\n", *it);
    return 0;
}