euclid 的扩展算法 C++
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12826114/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
euclid's extended algorithm C ++
提问by user1735851
I'm having an issue with Euclid's Extended Algorithm. (ax+by=gcd(a,b)) I'm trying to determine both the GCD and x and y. The GCD isn't a problem but using the loop method something is going wrong with x and y. Normally one number comes up as 0 and the other is an abnormally large negative number. Code follows:
我对 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;
}
采纳答案by GWW
Two of your assignments are wrong they should be:
你的两个任务是错误的，它们应该是：
temp2 = x;
x=lastx-q*x;
lastx = temp2;
temp3 = y;
y = lasty-q*y;
lasty=temp3;
Example output with the above fixes:
具有上述修复的示例输出：
Please input a
54
Please input b
24
gcd6
x=1
y=-2
回答by maruf
Although the question has been asked a long time ago, but the answer will help someone who were finding C++ implementation of extended euclidean algorithm.
虽然这个问题很久以前就有人问过了，但答案将帮助那些正在寻找扩展欧几里得算法的 C++ 实现的人。
Here is a recursive C++ implementation:
这是一个递归的 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;
}
Example with code:
代码示例：
#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;
}
Input:
输入：
a = 99, b =78
a = 99, b = 78
Output:
输出：
GCD: 3, x = -11, y = 14
GCD：3，x = -11，y = 14
