什麼是算法用於求解線性丟番圖方程：ax + by = c

我在這裏尋找整數解答。我知道它有無限多的來自第一對解決方案和gcd（a，b）| c的解決方案。但是，我們如何才能找到第一對解決方案？有沒有解決這個問題的算法？什麼是算法用於求解線性丟番圖方程：ax + by = c

感謝，
陳

來源

2011-02-06 Chan

您的網頁搜索產生了什麼？ – 2011-02-06 23:45:41

@David Heffernan：擴展的歐幾里德算法是我得到的，但我無法理解他們用一種非常奇怪的語言編寫的僞代碼。 – Chan 2011-02-07 00:16:50

注意，這裏並不總是一個解決方案。事實上，如果c是gcd(a, b)的倍數，那麼只有一個解決方案。

也就是說，你可以使用extended euclidean algorithm這個。

這是一個實現它的C++函數，假設c = gcd(a, b)。我更喜歡使用遞歸算法：如果你有c = k*gcd(a, b)與k > 0

function extended_gcd(a, b) 
    if a mod b = 0 
     return {0, 1} 
    else 
     {x, y} := extended_gcd(b, a mod b) 
     return {y, x-(y*(a div b))} 

int ExtendedGcd(int a, int b, int &x, int &y) 
{ 
    if (a % b == 0) 
    { 
     x = 0; 
     y = 1; 
     return b; 
    } 

    int newx, newy; 
    int ret = ExtendedGcd(b, a % b, newx, newy); 

    x = newy; 
    y = newx - newy * (a/b); 
    return ret; 
}

現在，公式變爲：

ax + by = k*gcd(a, b) (1) 
(a/k)x + (b/k)y = gcd(a, b) (2)

所以只要找到你的（2），或者找到解決方案解決方案（1）乘以x和y乘以k。

來源

2011-02-06 23:52:33 IVlad

什麼是算法用於求解線性丟番圖方程：ax + by = c

回答

相關問題