描述

已知多项式方程：

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

输入格式

第一行包含22个整数n、m、每两个整数之间用一个空格隔开。
接下来的n+1行每行包含一个整数，依次为a0,a1,a2,...,an

输出格式

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

样例一

input

2 10
1
-2
1

output

1
1

样例二

input

2 10
2
-3
1

output

2
1
2

样例三

input

2 10
1
3
2

output

0

限制与约定

对于30%的数据，0<n≤2，|ai|≤100，an≠0，m≤100；
对于50%的数据，0<n≤100，|ai|≤10100，an≠0，m≤100；
对于70%的数据，0<n≤100，|ai|≤1010000，an≠0，m≤10000；
对于100%的数据，0<n≤100，|ai|≤1010000，an≠0，m≤1000000。
时间限制：1s
内存限制：128MB

题解：

30分：模拟即可
100分：我们发现 a = 0 时，a % p == 0，但当 a % p == 0 时，a 不一定等于0，但当 p 很多且为素数时，就极有可能为0。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long LL;
int n, m;
//---------30--------------------------
int num[233], ans[233];
bool check(int mm)
{
	int ls = num[1] + num[2]*mm + num[3]*mm*mm;
	if (ls == 0)
		return 1;
	return 0;
}
//------------------------------------
//-------------100-----------
int t = 5;
LL pri[] = {0, 100003, 63443, 79087, 99901, 143651};
LL a[105][10];
bool used[1000007];
bool can[1000007][10];
void read(LL x)
{
	LL f = 1;
	char c = getchar();
	while (c < '0' || c > '9')
	{
		if (c == '-')
			f = -1;
		c = getchar();
	}
	while (c >= '0' && c <= '9')
	{
		for (int i = 1; i <= t; i++)
		{
			a[x][i] *= 10;
			a[x][i] += c-'0';
			a[x][i] %= pri[i];
		}
		c = getchar();
	}
	for (int i = 1; i <= t; i++)
		a[x][i] *= f;
}
bool find(LL x)
{
	bool h = 0;
	for (int k = 1; k <= t; k++)
	{
		LL ans = 0;
		for (int i = n; i >= 1; i--)
		{
			ans += a[i][k];
			ans *= x;
			ans %= pri[k];
		}
		ans += a[0][k];
		ans %= pri[k];
		if (ans)
		{
			can[x][k] = 1;
			h = 1;
		}
	}
	if (h)
		return 0;
	return 1;
}
int main()
{
	cin >> n >> m;
	if (n <= 2)
	{
		int cnt = 0, sum = 0;
		for (int i = 1; i <= n+1; i++)
			scanf("%d", &num[i]);
		for (int i = 1; i <= m; i++)
		{
			if (check(i))
				sum++, ans[++cnt] = i;
		}
		cout << sum << endl;
		for (int i = 1; i <= cnt; i++)
			cout << ans[i] << endl;
	}
	else
	{
		for (int i = 0; i <= n; i++)
			read(i);
		int cnt = 0;
		for (LL i = 1; i <= m; i++)
		{
			if (!used[i])
			{
				bool h = 0;
				for (int k = 1; k <= t; k++)
				{
					LL p = i % pri[k];
					if (can[p][k] == 1)
					{
						used[i] = 1;
						h = 1;
						break;
					}
				}
				if (h)
					continue;
				if (!find(i))
					used[i] = 1;
				else
					cnt++;
			}
		}
		printf("%d\n", cnt);
		for (int i = 1; i <= m; i++)
			if (!used[i])
				printf("%d\n", i);
	}
	return 0;
}