 |
 |
 |
| 24小時(shí)熱門(mén)版塊排行榜 |
- >論壇更新日志 (2015)
- >導(dǎo)師招生 (142)
- >蟲(chóng)友互識(shí) (132)
- >考研 (123)
- >考博 (32)
- >休閑灌水 (26)
- >招聘信息布告欄 (25)
- >博后之家 (18)
- >碩博家園 (16)
- >基金申請(qǐng) (12)
- >教師之家 (12)
- >論文投稿 (12)
- >文獻(xiàn)求助 (8)
- >找工作 (7)
- >公派出國(guó) (6)
- >醫(yī)學(xué) (5)
 |
 |
 |
||
 |
 |
 |
 |
 |
| 1 | 1/1 | 返回列表 |
| 查看: 797 | 回復(fù): 0 | |||
[交流]
多項(xiàng)式g,f，在模p意義下的最大公因數(shù)，
程序計(jì)算
|
const { trace } = require("console" ;function gcdModP(g, f, p) { let d = g.slice(); // 復(fù)制 g(x) 的系數(shù)到 d(x) 數(shù)組中 let r = f.slice(); // 復(fù)制 f(x) 的系數(shù)到 r(x) 數(shù)組中 while (!isZeroPoly(r)) { let t = trim(d); if (t.length < r.length) { [t, r] = [r, t] } // 復(fù)制 d(x) 的系數(shù)到 t(x) 數(shù)組中 for (let i = 0; i < r.length; i++) { let j1 = t.length - r.length + i; t[j1] = t[j1] || 0n let quotient = (t[j1] * modInverse(r, p)) % p; // 計(jì)算商 for (let j = 0; j < r.length; j++) { let index = t.length - r.length + i + j; // console.log(index) t[index] = t[index] || 0n t[index] -= quotient * r[j]; // 更新 t(x) 的系數(shù) t[index] = (t[index] % p + p) % p; // 取模 } // console.log(t); } d = r.slice(); // 復(fù)制 r(x) 的系數(shù)到 d(x) 數(shù)組中 r = t.slice(d.length - r.length + 1); // 復(fù)制 t(x) 的系數(shù)到 r(x) 數(shù)組中 // console.log(d, r); r = trim(r); } // 將 d(x) 的系數(shù)除以它的首項(xiàng)系數(shù)，確保它是首項(xiàng)系數(shù)為 1 的冪次多項(xiàng)式 let dLeadingCoefficient = d[d.length - 1]; for (let i = 0; i < d.length; i++) { d = (d * modInverse(dLeadingCoefficient, p)) % p; } return d; } function modInverse(a, p) { // 使用擴(kuò)展歐幾里得算法計(jì)算 a 在模 p 意義下的逆元 let [x, y] = extendedEuclideanAlgorithm(a, p); return (x % p + p) % p; } function extendedEuclideanAlgorithm(a, b) { // 擴(kuò)展歐幾里得算法返回 a 和 b 的最大公因數(shù) d，以及滿足 ax + by = d 的整數(shù) x 和 y if (b === 0n) { return [1n, 0n, a]; } let [x, y, d] = extendedEuclideanAlgorithm(b, a % b); return [y, x - (a / b) * y, d]; } /** * @param {Array<Number>} array */ function trim(array) { let i = 0; for (; i < array.length; i++) { // const element = array[index]; if (array != 0n) { break } } let j = array.length - 1; for (; j > 0; j--) { // const element = array[index]; if (array[j] != 0n) { break } } return array.slice(i, j + 1) } // console.log(trim([0n, 0n, 0n, 0n, 0n, 0n])); /** * 判斷一個(gè)多項(xiàng)式是否為 0。 * * @param {Array} poly - 待判斷的多項(xiàng)式 * @returns {boolean} 是否為 0 */ function isZeroPoly(poly) { for (let i = 0; i < poly.length; i++) { if (poly !== 0n) { return false; } } return true; } test() function test() { // console.log(modInverse(5n, 47n)); // console.log(trimStart([0n, 0n, 1n, 2n])) // 測(cè)試用例 1 let g1 = [6n, 2n]; let f1 = [17n, 15n]; let p1 = 7n; console.log("結(jié)果", gcdModP(g1, f1, p1)); // // 測(cè)試用例 3 let f3 = [3n, 1n, 3n, 1n]; let g3 = [3n, 1n]; // 3 + x let p3 = 101n; console.log("結(jié)果3", gcdModP(g3, f3, p3)); let f4 = [3n, 4n, 4n, 1n]; let g4 = [3n, 1n]; // 3 + x let p4 = 101n; console.log("結(jié)果4", gcdModP(g4, f4, p4)); } module.exports = { gcdModP } 多項(xiàng)式g,f，在模p意義下的最大公因數(shù)， 結(jié)果4為什么是1呀，有人幫忙解答下嗎 發(fā)自小木蟲(chóng)Android客戶端 |
回復(fù)此樓» 猜你喜歡
288求調(diào)劑
已經(jīng)有12人回復(fù)
-
化工284求調(diào)劑
已經(jīng)有10人回復(fù)
-
一志愿北京化工大學(xué)材料與化工296分求調(diào)劑
已經(jīng)有8人回復(fù)
-
2026級(jí)碩士研究生招生/調(diào)劑
已經(jīng)有5人回復(fù)
-
0703化學(xué)調(diào)劑
已經(jīng)有7人回復(fù)
-
新疆大學(xué)地質(zhì)與礦業(yè)工程學(xué)院招生
已經(jīng)有32人回復(fù)
-
0856材料與化工353分求調(diào)劑
已經(jīng)有4人回復(fù)
-
282分材料專業(yè)求調(diào)劑院校
已經(jīng)有13人回復(fù)
-
315食品工程求調(diào)劑
已經(jīng)有5人回復(fù)
-
環(huán)境調(diào)劑
已經(jīng)有3人回復(fù)
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 靈水墨 的主題更新
| 1 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 288求調(diào)劑 +9 | 王曉陽(yáng)- 2026-03-09 | 12/600 |
|
|---|---|---|---|---|
|
|
[考研] 315食品工程求調(diào)劑 +3 | Oreov0 2026-03-06 | 5/250 |
|
|
[考研] 標(biāo)題:撿漏預(yù)警|08工科/09農(nóng)學(xué)調(diào)劑!英語(yǔ)要求低，過(guò)線即有機(jī)會(huì)! +4 | 馬超放煙花 2026-03-07 | 4/200 |
|
|
|
[考研] 家人們 調(diào)劑不迷路 看這里 +8 | likeihood 2026-03-09 | 10/500 |
|
|
|
[考研]
 295復(fù)試調(diào)劑
+4
|
簡(jiǎn)木ChuFront 2026-03-09 | 4/200 |
|
|
|
[考研] 310 070300化學(xué)求調(diào)劑 +4 | 撲風(fēng)鈴的貓 2026-03-08 | 5/250 |
|
|
|
[考研] 求調(diào)劑 +3 | 鶴遨予卿 2026-03-09 | 3/150 |
|
|
|
[考研] 296求調(diào)劑 +4 | Xinyu Wu311 2026-03-09 | 4/200 |
|
|
|
[考博] 求材料讀博院校 +8 | yanglei131 2026-03-08 | 8/400 |
|
|
|
[考研] 材料調(diào)劑 +4 | xxxcm 2026-03-08 | 7/350 |
|
|
|
[考研] 求0856調(diào)劑 +5 | 小力氣珂珂 2026-03-08 | 5/250 |
|
|
|
[考研] 303求調(diào)劑 +8 | forgman95 2026-03-05 | 10/500 |
|
|
|
[考研] 346分材料求調(diào)劑 +5 | snow_反季節(jié)版 2026-03-07 | 5/250 |
|
|
|
[考研] 一志愿211 化學(xué)305分求調(diào)劑 +3 | 0703楊悅305分 2026-03-05 | 3/150 |
|
|
|
[考研] 2026調(diào)劑】考試A區(qū)0703化學(xué)類323分 誠(chéng)求接收 +3 | 卷柏卷柏 2026-03-05 | 4/200 |
|
|
|
[考研] 278求調(diào)劑 +5 | Gale1314 2026-03-06 | 5/250 |
|
|
|
[考博] 2026年博士名額撿漏 +4 | 科研ya 2026-03-04 | 7/350 |
|
|
|
[考研] 求調(diào)劑 +5 | danyyyy 2026-03-04 | 5/250 |
|
|
|
[考研] 求調(diào)劑 +3 | 泡了個(gè)椒 2026-03-04 | 4/200 |
|
|
|
[考研] 322,求調(diào)劑 +3 | 菜菜愛(ài)玩 2026-03-04 | 3/150 |
|