リニアディオパンチの方程式を解くのに使われるアルゴリズムは何ですか：ax + by = c

Question

ここでは整数解を探しています。私は、それが最初の対の解とgcd（a、b）| cから無限に多くの解を得ていることを知っています。しかし、どのようにして最初のソリューションのペアを見つけることができますか？この問題を解決するアルゴリズムはありますか？常に解決策がないことを

おかげで、
チャン

Answer 1

注意。実際には、の倍数のcがある場合にのみ解決策があります。

つまり、これにはextended euclidean algorithmを使用できます。

ここには、c = gcd(a, b)と仮定して、それを実装するC++関数があります。私は、再帰的なアルゴリズムを使用することを好む：あなたはk > 0でc = k*gcd(a, b)を持っている場合今

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を掛けます。