※ 引述《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/cn.aspx?n=bbs/Prob_Solve/M.1580578193.A.6BD.html ※ 编辑: LPH66 (123.195.194.58 台湾), 02/02/2020 01:34:35