洛谷P2312 解方程題解

題目描述

已知多項(xiàng)式方程：

\[a_0+a_1x+a_2x^2+\cdots+a_nx^n=0\]
求這個(gè)方程在 \([1,m]\) 內(nèi)的整數(shù)解（\(n\) 和 \(m\) 均為正整數(shù)）。

輸入格式

輸入共 \(n + 2\) 行。

第一行包含 \(2\) 個(gè)整數(shù) \(n, m\) ，每?jī)蓚€(gè)整數(shù)之間用一個(gè)空格隔開。

接下來(lái)的 \(n+1\) 行每行包含一個(gè)整數(shù)，依次為 \(a_0,a_1,a_2\ldots a_n\).

輸出格式

第一行輸出方程在 \([1,m]\) 內(nèi)的整數(shù)解的個(gè)數(shù)。

接下來(lái)每行一個(gè)整數(shù)，按照從小到大的順序依次輸出方程在 [1,m][1,m] 內(nèi)的一個(gè)整數(shù)解。

輸入輸出樣例

輸入 #1 復(fù)制

2 10
1
-2
1

輸出 #1 復(fù)制

1
1

輸入 #2 復(fù)制

2 10
2
-3
1

輸出 #2 復(fù)制

2
1
2

輸入 #3 復(fù)制

2 10
1
3
2

輸出 #3 復(fù)制

0
說(shuō)明/提示
對(duì)于 \(30%\) 的數(shù)據(jù)：\(0<n\le 2\),\(|a_i|\le 100\),\(a_n≠0\),\(m<1000\)
對(duì)于 \(50%\) 的數(shù)據(jù)：\(0<n\le 100,|a_i|\le 10^{100},a_n≠0,m<1000\)
對(duì)于 \(70%\) 的數(shù)據(jù)：\(0<n\le 100,|a_i|\le 10^{10000},a_n≠0,m<10^4\)。

對(duì)于 \(100%\) 的數(shù)據(jù)：\(0<n\le 100,|a_i|\le 10^{10000},a_n≠0,m<10^6\)。

解析：

秦九韶公式 + 快讀
輸入要注意，因?yàn)檩斎氲?span id="ze8trgl8bvbq" class="math inline">\(a[i]\)范圍比較大，
所以就對(duì)一個(gè)質(zhì)數(shù)取模
從\(1\)到\(m\)進(jìn)行枚舉，枚舉的是\(x\)，
然后利用秦九韶公式進(jìn)行求解
如果返回的值是\(0\)，那么就記錄
反之繼續(xù)。

#include <cstdio> #include <iostream> #include <cmath> #include <queue> #include <stack> #include <cstring> #include <vector> #include <algorithm> #include <iomanip> #define Max 105 #define re register #define D double #define int long long int n,m,a[Max],ans = 0, Ans[1000012]; const int mod = 19260817; int read() {char ch = getchar(); int f = 1, s = 0;while(ch < '0' || ch > '9') {if(ch == '-') f = -1;ch =getchar();}while(ch >= '0' && ch <= '9') {s = (10 * s + ch - '0') % mod;ch = getchar();}return s * f; } int work(int x) {int ANS = 0;for(re int i = n ; i >= 1 ; -- i)ANS = ((ANS + a[i]) * x)% mod;ANS = (ANS + a[0]) % mod;return ANS; } void Main() {scanf("%lld%lld",&n,&m);for(re int i = 0; i <= n; ++ i) a[i] = read();for(re int i = 1; i <= m; ++ i)if(work(i) == 0) ans ++, Ans[ans] = i;printf("%lld\n",ans);for(re int i = 1; i <= ans; ++ i) printf("%lld\n",Ans[i]); } signed main() {Main();return 0; }

轉(zhuǎn)載于:https://www.cnblogs.com/handsomegodzilla/p/11482644.html

總結(jié)

以上是生活随笔為你收集整理的洛谷P2312 解方程题解的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問(wèn)題。

如果覺(jué)得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。