※ 引述《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://webptt.com/m.aspx?n=bbs/Prob_Solve/M.1580578193.A.6BD.html ※ 編輯: LPH66 (123.195.194.58 臺灣), 02/02/2020 01:34:35