Re: [問題] 關於擴展歐幾里得算法
看板Prob_Solve (計算數學 Problem Solving)作者LPH66 (信じる力 奇跡起こすこと)時間4年前 (2020/02/02 01:29)推噓1(1推 0噓 0→)留言1則, 1人參與討論串2/2 (看更多)
※ 引述《nevikw39 (☆牜攵☆犬羊)》之銘言:
: 大家安安 o'_'o
: 最近在學習線性同餘方程,不太了解所謂擴展歐幾里得算法的過程。
: 以前學過一般歐幾里得法 aka 輾轉相除法,現在這個擴展推廣我明白所求是解出 a * x + b * y = gcd(a, b)。
: 以下是我根據網路查出的寫法:
: int exgcd(int a, int b, int &x, int &y)
: {
: if (!b)
: {
: x = 1;
: y = 0;
: return a;
: }
: int g = exgcd(b, a % b, y, x);
: y -= a / b * x;
: return g;
: }
: if 內的敘述我可以理解:當 b = 0 時 gcd(a, b) = a,此時 a*1 + b*0 = gcd(a, b)
: if 後的部分我就不太懂惹,如果算出 b*y' + (a%b)*x' = gcd(a, b),則如何求出
: a * _ + b * _ = gcd(a, b) ??
: y -= a / b * x 的意義是什麼呢??
: 感謝大家
a 除以 b 的商為 a / b, 餘為 a % b (這裡我把 / 當成整數除法)
也就是說我們有 a % b = a - (a / b) * b (餘數 = 被除數 - 商 * 除數)
那麼代入 gcd(a, b) = b*y' + (a%b)*x'
= b*y' + [a - (a/b) * b]*x'
= b*y' + a*x' - (a/b)*b*x'
= a*x' + b*(y' - (a/b)*x)
﹌﹌﹌↑﹌﹌﹌
這就是新的 y 了
--
將很小又單純的命令《Code》組合成函數《Function》。函數累積成更大更方便的元件《
Parts》,成為程式《App》。接著進行動態結合,相互通訊,打造出服務《Service》。
李奧納多知道,要得到結果,就必須持續進行非常單純的作業。為了展現出匹敵巨大建築
的技術,現在非得將面前的碎片組合起來。
知道這條路多麼遙遠的人,叫做極客《Geek》。
將這份尊貴具體呈現的人,叫做駭客《Hacker》。 --記錄的地平線 Vol.9 p.299
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 123.195.194.58 (臺灣)
※ 文章網址: https://www.ptt.cc/bbs/Prob_Solve/M.1580578193.A.6BD.html
※ 編輯: LPH66 (123.195.194.58 臺灣), 02/02/2020 01:34:35
推
02/02 12:20,
4年前
, 1F
02/02 12:20, 1F
討論串 (同標題文章)
本文引述了以下文章的的內容:
完整討論串 (本文為第 2 之 2 篇):
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章