 |
 |
 |
 |
 |
 |
||
 |
 |
 |
 |
 |
| 1 | 1/1 | 返回列表 |
| 查看: 793 | 回復(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])) // 測試用例 1 let g1 = [6n, 2n]; let f1 = [17n, 15n]; let p1 = 7n; console.log("結(jié)果", gcdModP(g1, f1, p1)); // // 測試用例 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ā)自小木蟲Android客戶端 |
回復(fù)此樓» 猜你喜歡
求調(diào)劑
已經(jīng)有3人回復(fù)
-
A區(qū)一本交叉課題組，低分調(diào)劑，招收機(jī)械電子信息通信等交叉方向
已經(jīng)有20人回復(fù)
-
334求調(diào)劑
已經(jīng)有5人回復(fù)
-
085600材料與化工，一志愿廣州985，求調(diào)劑
已經(jīng)有4人回復(fù)
-
334求調(diào)劑
已經(jīng)有4人回復(fù)
-
紡織、生物、化學(xué)、材料等專業(yè)
已經(jīng)有7人回復(fù)
-
材料學(xué)學(xué)碩308分/本科東北大學(xué)/一志愿西北工業(yè)大學(xué)/
已經(jīng)有8人回復(fù)
-
0856材料與化工求調(diào)劑！
已經(jīng)有8人回復(fù)
-
一志愿武理085601專碩347分求調(diào)劑
已經(jīng)有4人回復(fù)
-
招調(diào)劑
已經(jīng)有6人回復(fù)
相關(guān)版塊跳轉(zhuǎn)
我要訂閱樓主 靈水墨 的主題更新
| 1 | 1/1 | 返回列表 |
| 最具人氣熱帖推薦 [查看全部] | 作者 | 回/看 | 最后發(fā)表 | |
|---|---|---|---|---|
|
[考研] 一志愿武理085601專碩347分求調(diào)劑 +3 | 啊歐歐歐 2026-03-04 | 4/200 |
|
|---|---|---|---|---|
|
|
[考研] 302材料工程求調(diào)劑 +7 | Doleres 2026-03-01 | 8/400 |
|
|
|
[考研] 085600材料調(diào)劑 總分330 +5 | 池池丶 2026-03-03 | 5/250 |
|
|
[考研] 304求調(diào)劑 +7 | 曼殊2266 2026-02-28 | 8/400 |
|
|
|
[考研] 化學(xué)工程求調(diào)劑 +10 | 化工人999 2026-03-04 | 10/500 |
|
|
|
[考研] 學(xué)碩材料275調(diào)劑 +9 | 路三三 2026-03-03 | 9/450 |
|
|
|
[考研] 本科太原理工采礦工程，求調(diào)劑 +3 | onlx 2026-03-01 | 3/150 |
|
|
|
[考研] 325求調(diào)劑 +5 | 學(xué)家科 2026-03-04 | 5/250 |
|
|
|
[考研] 264求調(diào)劑 +3 | thext 2026-03-03 | 3/150 |
|
|
|
[考研] 291求調(diào)劑 +4 | Afy123456 2026-03-03 | 7/350 |
|
|
|
[考研] 環(huán)境調(diào)劑 +8 | chenhanheng 2026-03-02 | 8/400 |
|
|
|
[考研] 266材料化工求調(diào)劑 +3 | 哇塞王帥 2026-03-03 | 3/150 |
|
|
|
[考研] 0805總分292，求調(diào)劑 +12 | 幻想之殤 2026-03-01 | 12/600 |
|
|
|
[考研] 一志愿中科大能動(dòng)297求調(diào)劑，本科川大 +3 | 邵11 2026-03-03 | 3/150 |
|
|
|
[考研] 求調(diào)劑 +4 | Guo_yuxuan 2026-03-02 | 5/250 |
|
|
|
[考研] 清華大學(xué) 材料與化工 353分求調(diào)劑 +5 | awaystay 2026-03-02 | 6/300 |
|
|
|
[考研] 338求調(diào)劑 +5 | 18162027187 2026-03-02 | 6/300 |
|
|
|
[考研] 0856材料調(diào)劑 +5 | 沿岸有貝殼OUC 2026-03-02 | 5/250 |
|
|
|
[考研] 材料學(xué)調(diào)劑 +10 | 提神豆沙包 2026-02-28 | 12/600 |
|
|
|
[論文投稿]
求助coordination chemistry reviews 的寫作模板
 10+3
|
ljplijiapeng 2026-02-27 | 4/200 |
|