洛谷P2312解方程题解

题目

暴力能得\(30\)，正解需要其他的算法操作，算法操作就是用秦九韶算法来优化。

秦九韶算法就是求多项式的值时，首先计算最内层括号内一次多项式的值，然后由内向外逐层计算一次多项式的值，然后就将求\(n\)次多项式的算法转化为求\(n\)个一次多项式的算法。

但是这样只能得到30分，用高精也只能拿50分，所以此时可以用模数意义下的\(hash\)来解决，设置模数为1e9+7(或者其他比较大的模数)，就可以来优化时间，虽然有很可能会错，但是还是可以用很快的时间来解决，且错的几率是非常的小的。

#include <bits/stdc++.h>

#define N 100100

#define mod 1000000007

#define ll long long

using namespace std;

ll n, m, ans, a[N], x[N];

bool flag = 0;

inline ll read()

{

	char ch; ll sum = 0, fu = 1; ch = getchar();

	while (ch < '0' || ch > '9') {

		if (ch == '-') fu = -1;

		ch = getchar();

	}

	while (ch >= '0' && ch <= '9') {

		sum =  ( (sum * 10) + ch - '0') % mod;

		ch = getchar();

	}

	return sum * fu;

}

bool check(ll now) {

	ll sum = 0;

	for (int i = n; i >= 0; i--)

		sum = (  (sum + a[i]) * now ) % mod;

	if (sum) return 0;

	else return 1;

}

int main()

{

 	scanf("%lld%lld", &n, &m);

 	for (int i = 0; i <= n; i++)

 		a[i] = read();

 	/*

 	for (int i = 0; i <= n; i++)

		printf("%lld ", a[i]);

		*/

	for (int i = 1; i <= m; i++)

 		if ( check (i) )

 			x[++ans] = i, flag = 1;

 	if (!flag)

 		printf("0"), exit(0);

 	printf("%lld\n", ans);

 	for (int i = 1; i <= ans; i++)

 		printf("%lld\n", x[i]);

}