Description
已知多项式方程：a0+a1x+a2x^2+…+an*x^n=0
求这个方程在[1,m]内的整数解（n和m均为正整数）。
第一行包含2个整数n、m，每两个整数之间用一个空格隔开。
接下来的n+1行每行包含一个整数，依次为a0,a1,a2,…,an。
Output
第一行输出方程在[1,m]内的整数解的个数。
接下来每行一个整数，按照从小到大的顺序依次输出方程在[1,m]内的一个整数解。
2 10
2
-3
1
Sample Output
2
1
2
HINT
对于100%的数据，1≤n≤100，|ai|≤1010000，an≠0，m≤1000000。
Solution
RP题，看你随机素数生成的好不好了。
考虑一个多项式，如果\(A(x)=0\)，则\(A(x) % p=0\)，反之若\(A(x) % p=0\)，那么就有很大的几率\(A(x)=0\)。
我们取几个素数，对于每个素数p，我们看小于等于他的所有整数i是不是符合上述条件，也就是看\(A(i)\)是否为0，如果不为零，则所有的\(A(i+k*p)\)也等于0了。
然后我们惊奇地发现成绩许多大犇这道题都是95…
是hash模数取跪了的原因…
Code
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
50
51
52
53
54
| /**************************************************************
Problem: 3751
User: MagHSK
Language: C++
Result: Accepted
Time:7016 ms
Memory:3784 kb
****************************************************************/
#include <cstdio>
#include <cstring>
typedef long long ll;
char a[105][10005];
const int prime[5] = {22349,22367,22369,17389,21893};
int n, m, cnt, l[105];
int b[105];
bool dayuling[105];
bool vis[2000005];
void B(ll mod) {
for (int i = 0; i <= n; ++i) {
b[i] = 0;
for (int j = 0; j < l[i]; ++j) b[i] = (b[i] * 10 - '0' + a[i][j]) % mod;
if (!dayuling[i]) b[i] = -b[i];
}
}
int tot = 0;
int main() {
scanf("%d%d", &n, &m);
memset(vis, 0, sizeof(vis));
for (int i = 0; i <= n; ++i) {
scanf("%s", a[i]);
l[i] = strlen(a[i]);
if(a[i][0] == '-') {
dayuling[i] = false;
for (int j = 0; j < l[i]; ++j)
a[i][j] = a[i][j+1];
l[i]--;
}
else dayuling[i] = true;
}
int tmp;
for (int j = 0; j < 5; ++j) {
B(prime[j]);
for (int i = 1; i <= prime[j]; ++i) {
tmp = 0;
for (int k = n; k >= 0; --k) tmp = (tmp * i + b[k]) % prime[j];
if (tmp) for (int k = 0; i + k * prime[j] <= m; k++) vis[i + k * prime[j]] = true;
}
}
for (int i = 1; i <= m; ++i) if (!vis[i]) ++tot;
printf("%d\n", tot);
for (int i = 1; i <= m; ++i) if (!vis[i]) printf("%d\n", i);
return 0;
}
|