解方程

题目

已知多项式方程:

$$ a[0] + a[1] x + a[2] x^2 + …… + a[n] * x^n = 0 $$

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

格式

输入格式

输入共 n+2 行。
第一行包含 2 个整数 n、m,每两个整数之间用一个空格隔开。
接下来的 n+1 行每行包含一个整数,依次为a[0], a[1], a[2], …… a[n];

输出格式

第一行输出方程在[1, m]内的整数解的个数。
接下来每行一个整数,按照从小到大的顺序依次输出方程在[1, m]内的一个整数解。

样例

样例输入

2 10

1

-2

1

样例输出

1

1

数据范围

对于30%的数据0<n<=2, |a[i]|<=100, a[n]!=0, m<=100;

对于50%的数据0<n<=100, |a[i]|<=10^100, a[n]!=0, m<=100;

对于70%的数据0<n<=100, |a[i]|<=10^10000, a[n]!=0, m<=10000;

对于100%的数据0<n<=100, |a[i]|<=10^10000, a[n]!=0, m<=1000000;

思路

对于等式如果两边都同时%上一个数p 等式依然成立

$$ (a[0] + a[1] x + a[2] x^2 + …… + a[n] * x^n) % p = 0 % p = 0 $$

所以可以压低a[]数组

小技巧 : 在解方程时需要改变原式 不能直接求x^n

$$ a[0] + a[1] x + a[2] x^2 + a[3] x^3 = ((a[3] x + a[2]) x + a[1]) x + a[0] $$

代码如下

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
55
56
57
58
#include <iostream>
#include <cstring>
#include <string>
#include <cstdio>
#include <cmath>
#define LL long long
using namespace std;
int n, m;
string s;bool can[1000005];
LL p[3] = {0, 67891, 1000000007};
LL a[3][105];
inline void mo(string x, int y)
{
bool F = false;
int size = x.size();
for (int i=1; i<=2; i++)
{
int j = 0;
if (x[0] == '-') F = true, j = 1;
for (; j<size; j++)
a[i][y] = (a[i][y] * 10ll % p[i] + x[j] - '0');
if (F == true) a[i][y] = p[i] - a[i][y];
}
}
inline bool pd(int x, int y)
{
LL num = n-1, ret = a[y][n];
while(num >= 0)
{
ret = ret * x % p[y] + a[y][num];
ret %= p[y];
num --;
}
return ret % p[y];
}
int main()
{
scanf("%d%d", &n, &m);
for (int i=0; i<=n; i++)
{
cin >> s;
mo(s, i);
}
for (int i=1; i<=p[1]; i++)
{
if (!pd(i, 1))
{
for (int j = i; j<=m; j+=p[1])
if(!pd(j, 2))
can[j] = 1;
}
}
int ans = 0;
for (int i=1; i<=m; i++) if (can[i]) ans++;
printf("%d\n", ans);
for (int i=1; i<=m; i++) if (can[i]) printf("%d\n", i);
return 0;
}