前言

​ 这篇文章我将介绍两个最大公约数的算法并讲解一些题目。有错的地方，请大家多多包涵。

介绍

​ 最大公约数（最大公因数）指的就是可以同时被整数a和b整除的最大数（百度百科链接）。用代码来求最大公约数一般用这两种思想。

  • 辗转相除法：也称欧几里德算法。

  • 更相减损法：也称更向减损术。

算法实现

辗转相除法

​ 设两个整数a和b（这里默认a>b）。a%b得到整数c，然后a=c如果换完后a<b那么a b互换后再进行上面的操作直到出现整数a被整数b整除。这时候的整数b就是最大的公约数。它的证明太复杂了，我感觉这个链接中的证明就很好了。所以我这里就不证明了。

辗转相除发的算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
int __gcd(int a, int b)
{
	if (a%b==0)//如果可以a可以被b整除就意味着b就是最大公约数
	{
		return b;
	}
	else
	{
		a = a % b;
		if (a>b)//如果a小于b那么a%b会一直为a，函数就会进行死循环
		{
			return __gcd(a, b);
		}
		else
		{
			return __gcd(b, a);
		}
	}
}

在有些编译器中直接就有**__gcd()这个函数，在#include**头文件中。但是我用visual studio 2019就没有调出来过。

更相减损法

​ 设两个整数a和b（这里默认a>b）。如果a和b都能被2整除则就把他们都除以2。然后用a减去b得到c，让c=a。接下来调换a与b的数值使得a>b。最后重复上面的步骤直到c=b。如果之前没有约简则直接输出b否则要将b乘上约简的值。

​ 比如12，4。两个都是偶数所以进行约简。一直除与2直到它们中的一个不是偶数则得到3，1。最终进行减，结果必是b=1.但是你应该要输出4*b。

更相减损法的算法实现

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
int gcd(int a, int b)
{
	int count = 0;
	while (a%2==0&&b%2==0)//先判断是否两个都可以用2约简
	{
		a = a / 2;
		b = b / 2;
		count = count + 2;
	}
	while (a!=b)//一直执行a-b直到a等于b
	{
		if (a < b)//让a一定大于b
		{
			int t = b;
			b = a;
			a = t;
		}
		a = a - b;
	}
	if (count==0)//因为后面要输出count*a，所以如果count=0就要让它为1
	{
		count = 1;
	}
	return count * a;
}

两种算法的实现我都展示出来了，当然你也不一定要按我的写法来做。比如辗转相除法我用递归来写，你可以不用递归也能写出来。总之对于算法我们还是要先记住它的思想而不是具体的实现。

实例

HUD-2504 又见GCD

Problem Description

有三个正整数a,b,c(0<a,b,c<10^6)，其中c不等于b。若a和c的最大公约数为b，现已知a和b，求满足条件的最小的c。

Input

第一行输入一个n，表示有n组测试数据，接下来的n行，每行输入两个正整数a,b。

Output

输出对应的c，每组测试数据占一行。

Sample Input

1
2
3
2
6 2
12 4

Sample Output

1
2
4
8

Source

《ACM程序设计》短学期考试_软件工程及其他专业

Recommend

lcy | We have carefully selected several similar problems for you: 2502 2503 2500 1215 2501

对于又见GCD的分析

​ 本题就是让我们知道最大公约数c和一个值a然后让我们求得值b。b是满足c是a和b的最大公约数条件下的最小值且它不等于c。那么c是b的最大公约数。那么b必定是c的倍数。那么我们只要设一个整数i等于2开始进行ic然后用求最大公约数的算法进行判断ic和a的最大公约数是否为又见GCD。是则输出**i*c否则i++**。

AC代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
#include<iostream>
#include<algorithm>
#include<cmath>
using namespace std;
int __gcd(int a, int b)
{
	if (a%b==0)//如果可以a可以被b整除就意味着b就是最大公约数
	{
		return b;
	}
	else
	{
		a = a % b;
		if (a>b)//如果a小于b那么a%b会一直为a，函数就会进行死循环
		{
			return __gcd(a, b);
		}
		else
		{
			return __gcd(b, a);
		}
	}
}
int main()
{
	int a, b, c,t;
	while (cin>>t)
	{
		while (t--)
		{
			cin >> a >> c;
			int i = 2;//因为c！=b且b是c的倍数，所以i从2开始就好了
			while (__gcd(a, i * c) != c)//判断i*c是否符合条件
			{
				i++;
			}
			cout << i * c << endl;
		}
	}
	return 0;
}

（这题我使用更相减损法超时了所以我才用辗转相除法。）