洛谷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]); }

转载于:https://www.cnblogs.com/liuwenyao/p/11001560.html

总结

以上是生活随笔为你收集整理的洛谷P2312解方程题解的全部内容，希望文章能够帮你解决所遇到的问题。

如果觉得生活随笔网站内容还不错，欢迎将生活随笔推荐给好友。