贊助廠商

娛樂城推薦

首頁

刊登資訊

  • 刊登者:匿名
  • 時間:2021-06-19 19:10:03

尚未解答計算數學 Problem Solving- 關於擴展歐幾里得算法

計算數學 Problem Solving- 關於擴展歐幾里得算法

大家安安 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 的意義是什麼呢??

感謝大家

--

0個答案 計算數學 Problem Solving- 關於擴展歐幾里得算法

其他問題

友站連結