[問題] 關於擴展歐幾里得算法
看板Prob_Solve (計算數學 Problem Solving)作者nevikw39 (☆牜攵☆犬羊)時間4年前 (2020/02/01 22:53)推噓0(0推 0噓 0→)留言0則, 0人參與討論串1/2 (看更多)
大家安安 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://www.ptt.cc/bbs/Prob_Solve/M.1580568828.A.D17.html
討論串 (同標題文章)
以下文章回應了本文：
完整討論串 (本文為第 1 之 2 篇)：
Prob_Solve 近期熱門文章
PTT數位生活區 即時熱門文章
