在数学计算中经常会碰到计算最大公约数的情况，本文介绍两种最常用的计算方法。这两种方法在CSP等程序设计竞赛中也经常用到。

更相减损术

算法介绍

这种方法出自中国古代的数学专著《九章算术》，《九章算术》作者已不可考，它总结了战国、秦、汉时期的数学成就，主要是用于生产生活的一些实用算术。三国时期，刘徽为本书做了注解，目前流行的就是刘徽注本。

更相减损术原本是用来约分的，因此，也适用于计算最大公约数。原文如下：

可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。

现代译文：

（对于可以约分的分数来说，）可以折半的话，就折半（即，用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。

上文中，这个相等的数字\( \times 2^n=\)两数的最大公约数，\(n\)为折半次数。

C++程序

1、递归算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15

#include<iostream>
using namespace std;
int gcd(int a, int b){
    if(a == b) return a;
	else(a > b) a -= b;
	else b -= a;
	return gcd(a,b);
    }
        
int main(){
    int a, b;
    cin>>a>>b;
    cout<<gcd(a,b)<<endl;
    return 0;
    }

此方法的缺点：当a和b的差距较大（如100000倍）时，会导致错误（递归栈过深）。在C++程序设计中，还可以使用非递归方式来进行计算。

2、非递归算法

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16

#include <iostream>
using namespace std;
int main()
{　
    int a,b;　
    cin>>a>>b;　
    while(a != b)　
    {　
        if(a > b)　
            a -= b;　
        else　
            b -= a;　
     }　
     cout<<a<<endl;　
     return 0;　
}

在a和b差距较大时，效率较低。在程序竞赛中，不建议使用此方法。

辗转相除法

在小学生数学竞赛（小学奥数）中，培训机构都是教的这种方法。这种方法效率高，程序时间复杂度低，几乎每种算法书中也都介绍这种方法。下面来记录这种算法，也是给自己做一个备忘录。

辗转相除法也叫欧几里得算法，出自古希腊数学家欧几里得在其著作《The Elements》，所以被命名为欧几里得算法。

算法介绍

假设有两个正整数 \(a\) 和 \(b\)(其中 \(a \)不小于 \(b\)) ，记 \(a\) 除以\(b\)的余数为 \(r\)，那么 \(a\) 可以写成这样的形式：$$a=t\times b+r$$其中\(t\)是整数。

假设\(a\)和\( b \)有一个公约数\(u\)，则\(a\)和\(b\)都能够被\(u\)整除，即$$a=m\times u$$$$b=n\times u$$其中\(m\)和\(n\)都是整数。

则有$$r=a-t\times b = m\times u-t\times n\times u=(m-tn)\times u$$\(r\)也能被\(u\)整除。

推论

\(a\) 和 \(b\) 的约数的集合，全等于 \(b\) 和 \(r\) 的约数的集合。

\(a\) 和 \(b\) 的最大公约数，就是 \(b\) 和 \(r\) 的最大公约数。

对上述 \(a\) 和 \(b\) 辗转相除，递推为

$$a\div b=t \cdots \cdots r$$

$$b\div r=t_1 \cdots \cdots r_1$$

$$r\div r_1=t_2 \cdots \cdots r_2$$

$$r_1\div r_2=t_3 \cdots \cdots r_3$$

$$\cdots \cdots $$

$$r_{n-3}\div r_{n-2}=t_{n-1} \cdots \cdots r_{n-1}$$

$$r_{n-2}\div r_{n-1}=t_n \cdots \cdots 0$$

此时 \(r_{n−2}\) 和 \(r_{n−1}\)的约数就只有：\(r_{n−1}\) 和 \(r_{n−1}\) 的因数，所以他们的最大公约数就是 \(r_{n−1}\)，所以 \(r_{n−1}\)就是 \(a\) 和 \(b\) 的最大公约数。

C++程序

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

#include<iostream>
using namespace std;
int gcd(int a, int b){
    if(a % b == 0) return b;
	else return(b,a%b);
    }
        
int main(){
    int a, b;
    cin>>a>>b;
    cout<<gcd(a,b)<<endl;
    return 0;
    }

image