作者nevikw39 (☆牜攵☆犬羊)
看板Prob_Solve
标题[问题] 关於扩展欧几里得算法
时间Sat Feb 1 22:53:44 2020
大家安安 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 的意义是什麽呢？？
感谢大家
--
※ 发信站: 批踢踢实业坊(ptt.cc), 来自: 106.107.240.150 (台湾)
※ 文章网址: https://webptt.com/cn.aspx?n=bbs/Prob_Solve/M.1580568828.A.D17.html