欧几里得算法

简介

欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

假如需要求 1997 和 615 两个正整数的最大公约数,用欧几里德算法，是这样进行的：

1997 / 615 = 3 (余 152)

615 / 152 = 4(余7)

152 / 7 = 21(余5)

7 / 5 = 1 (余2)

5 / 2 = 2 (余1)

2 / 1 = 2 (余0)

至此，最大公约数为1

代码实现

那么采用代码实现它

非递归实现

#include <bits/stdc++.h>
using namespace std;

int main(){
	int a,b;
	cin >> a >> b;
	int yu = 0;
	while(a % b){
		yu = a % b; 
		a = b;
		b = yu;
	}
	cout<<b;
}

递归实现

#include <bits/stdc++.h>
using namespace std;

int gcd(int a,int b){
	if(b)
		return gcd(b, a % b);
	else
		return a;
}
int main(){
	int a,b;
	cin >> a >> b;
	cout<<gcd(a, b)<<endl;
}

递归精简

#include <bits/stdc++.h>
using namespace std;

int gcd(int a,int b){
	return b ? gcd(b , a % b) : a;
}

int main(){
	int a,b;
	cin >> a >> b;
	cout<<gcd(a, b)<<endl;
}

延伸

通过此方法快速求得最小公倍数

将两个数同时除以最大公约数，分别得到$n_1$与$n_2$，接着将最大公约数与$n_1,n_2$相乘即可得到最小公倍数

求最小公倍数

#include <bits/stdc++.h>
using namespace std;

int gcd(int a,int b){
	return b ? gcd(b , a % b) : a;
}

int main(){
	int a,b;
	cin >> a >> b;
	cout<<"最小公倍数:"<< ( a/gcd(a, b)) * (b/gcd(a, b) * gcd(a, b) )<<endl;
}

扩展

扩展欧几里德算法是用来在已知$a$, $b$求解一组$x$，$y$ 使得$ax+by =c$. (若c % gcd(a, b) != 0）则无解。一般会给定$c$是该式子求得最小正数，那么求满足条件的$x，y$。
#include <bits/stdc++.h>
using namespace std;

int exgcd(int a, int b, int &x, int &y){
	if(!b){
		x = 1,y = 0;
		return a;
	}
	int d = exgcd(b, a % b, y, x);
	y -= (a/b) * x;
	return d;
}

int main(){
	int a,b,x,y;
	cin >> a >> b;
	int d = exgcd(a, b, x, y);
	printf("%d * %d + %d * %d =%d\n", a, x, b, y, d);
}