ユークリッドの拡張アルゴリズムC++

Question

ユークリッドの拡張アルゴリズムに問題があります。 （ax + by = gcd（a、b））私はGCDとxとyの両方を決定しようとしています。 GCDは問題ではありませんが、ループメソッドを使用すると、xとyに問題が起こります。通常、1つの数字は0になり、もう1つは異常に大きな負の数字になります。コードは次のとおりです。

はあなたの割り当ての

#include <iostream> 

using namespace std; 

main() 
{ 
    int a,b,q,x,lastx,y,lasty,temp,temp1,temp2,temp3; 
    cout << "Please input a" << endl; 
    cin >> a; 
    cout << "Please input b" << endl; 
    cin >> b; 
    if (b>a) {//we switch them 
     temp=a; a=b; b=temp; 
    } 
    //begin function 
    x=0; 
    y=1; 
    lastx=1; 
    lasty=0; 
    while (b!=0) { 
     q= a/b; 
     temp1= a%b; 
     a=b; 
     b=temp1; 

     temp2=x-q*x; 
     x=lastx-q*x; 
     lastx=temp2; 

     temp3=y-q*y; 
     y=lasty-q*y; 
     lasty=temp3; 
    } 

    cout << "gcd" << a << endl; 
    cout << "x=" << lastx << endl; 
    cout << "y=" << lasty << endl; 
    return 0; 
} 

Answer 1

2つは間違っている、彼らは次のようになります。上記の修正を

temp2 = x; 
    x=lastx-q*x; 
    lastx = temp2; 

    temp3 = y; 
    y = lasty-q*y; 
    lasty=temp3; 

出力例：

Please input a 
54 
Please input b 
24 
gcd6 
x=1 
y=-2 

Answer 2

質問は長い時間を尋ねてきたが、しかし、その答えは、拡張されたユークリッドアルゴリズムのC++実装を見つける人を助けるでしょう。ここ

は、再帰C++インプリメンテーションである：コードで

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

    int x1, y1, gcd = xGCD(b, a % b, x1, y1); 
    x = y1; 
    y = x1 - (a/b) * y1; 
    return gcd; 
} 

例：

#include <iostream> 

int main() 
{ 
    int a = 99, b = 78, x, y, gcd; 

    if(a < b) std::swap(a, b); 

    gcd = xGCD(a, b, x, y); 
    std::cout << "GCD: " << gcd << ", x = " << x << ", y = " << y << std::endl; 

    return 0; 
} 

入力：

= 99、B = 78

出力：

GCD：3、X = -11、yは14