[NOIP 2014] 解方程

题目大意

已知多项式方程:

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

求这个方程在 [1,  m][1, \; m] 内的整数解(nnmm 均为正整数)。

1n1001 \leqslant n \leqslant 100

ai1010,000|a_i| \leqslant 10^{10,000}

1m1,000,0001 \leqslant m \leqslant 1,000,000

题目链接

【NOIP 2014】解方程 - LibreOJ 2503

题解

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

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

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

代码

这是 BZOJ 上 AC 的,UOJ 上的质数是 1493914939,150193,15019352852375285237

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

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;
}