題目

暴力能得\(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解方程题解的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。