题意概述

• 给定两个自然数
• 要求给出他们的最大公约数

方法一：更相减损术

思路与具体做法

• 更相减损术介绍

• 《九章算术》原文： 可半者半之，不可半者，副置分母、子之数，以少减多，更相减损，求其等也。以等数约之。
• 白话文译文：（如果需要对分数进行约分，那么）可以折半的话，就折半（也就是用2来约分）。如果不可以折半的话，那么就比较分母和分子的大小，用大数减去小数，互相减来减去，一直到减数与差相等为止，用这个相等的数字来约分。
• 两个数的最大公约数等于它们中较小的数和两数之差的最大公约数。

• 证明(反证法)
  • 假设$k1k1$k1,$(k2-k1)(k2-k1)$(k2−k1)不互质，
  • 令$gcb(k1,k2-k1)=mgcb(k1,k2-k1)=m$gcb(k1,k2−k1)=m(m为正整数且m>1);
  • $k1=m\ast ak1=m*a$k1=m∗a,$k2-k1=m\ast bk2-k1=m*b$k2−k1=m∗b
  • $k2=(a+b)mk2=(a+b)m$k2=(a+b)m
  • 即$k1k1$k1,$k2k2$k2有公约数$mm$m，与$k1k1$k1,$k2k2$k2互质矛盾
  • 所以假设不成立
  • 即$k1k1$k1,$(k2-k1)(k2-k1)$(k2−k1)互质
  • 所以$gcb(x,x-y)=d=gcb(x,y)gcb(x,x-y)=d=gcb(x,y)$gcb(x,x−y)=d=gcb(x,y)
  • 综上，$gcd(x,y)=gcd(x,y-x)gcd(x,y)=gcd(x,y-x)$gcd(x,y)=gcd(x,y−x)
  • 命题得证
• 实现
  • 不断用被减数和减数中的最小值，与差相减，直到所得的减数和差相等为止，这时这个相等的数即为最大公约数。 迭代版本

class Solution {//迭代版本 
public:
    int gcd(int a, int b) {
    	int temp;
		while(temp=abs(a-b),temp!=0){//不断用被减数和减数中的最小值，与差相减，直到为0
			b=min(a,b);//两数中的最小值
			a=temp;//差
		} 
		return a; 
    }
};

递归版本

class Solution {//递归版本 
public:
    int gcd(int a, int b) {
        return !a?b:gcd(abs(a-b),min(a,b));//以差和最小数反复做减法运算，直到余数为0 
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(max\right(a,b\left)\right)O(max(a,b))$O(max(a,b))，最坏情况下，减数为1，需要一个一个减完
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间使用

方法二：辗转相除法

思路与具体做法

• 辗转相除法介绍

• 古希腊数学家欧几里得在其著作《The Elements》中最早描述了这种算法,所以被命名为欧几里得算法。
• 定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。

• 证明
  • $aa$a可以表示成$a=kb+ra=kb+r$a=kb+r（a，b，k，r为正整数，且k和r分别为a除以b得到的商和余数)
  • 则有$r=a-kbr=a-kb$r=a−kb成立，假设$dd$d为$aa$a和$bb$b的一个公约数
  • 等式右边除以$dd$d，可以将$dd$d作为一个公因子提出来，即$dd$d也是$rr$r的一个约数
  • 因此d也是$bb$b,$amodba\; mod\; b$amodb的公约数。
  • 因$(a,b)(a,b)$(a,b)和$(b,amodb)(b,a\; mod\; b)$(b,amodb)的公约数相等，则其最大公约数也相等，得证。
• 实现
  • 以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数 迭代版本

class Solution {//迭代版本 
public:
    int gcd(int a, int b) {
    	int temp;
		while(temp=max(a,b)%min(a,b),temp!=0){//不断用除数和余数反复做除法运算，直到余数为0 
			a=b;//除数 
			b=temp;//余数 
		} 
		return b; 
    }
};

递归版本

class Solution {//递归版本 
public:
    int gcd(int a, int b) {//a代表被除数，b代表除数 
        return !b?a:gcd(b,a%b);//以除数和余数反复做除法运算，直到余数为0 
    }
};

时间复杂度和空间复杂度分析

• 时间复杂度：$O\left(2_{}min(a,b)\right)O(\backslash log\_\{2\}\{min(a,b)\}\; )$O(log2​min(a,b))，欧几里得算法指数级增长
• 空间复杂度：$O\left(1\right)O(1)$O(1)，无额外空间使用