euclid的扩展算法C++

Question

我遇到了Euclid的扩展算法问题。 （ax + by = gcd（a，b））我试图确定GCD和x和y。 GCD不是问题，但使用循环方法x和y有问题。通常一个数字为0，另一个数字为一个异常大的负数。代码如下：

#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

你的作业中有两个是错的，他们应该是：

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; 
} 

输入：

A = 99，B = 78

输出：

GCD：3，X = -11，Y = 14