【牛客题霸题解】最大公约数

我们用辗转相除法（又称欧几里得算法）来计算两个数的最大公约数 (Greatest Common Divisor)所以下文用gcd(a,b)表示a和b的最大公约数。

先举一个例子： 假如需要求 434 和 652 的最大公约数,用欧几里得算法，是这样进行的： 434 / 652 = 0 (余 434) 652 / 434 = 1(余218) 434 / 218 = 1(余216) 218 / 216 = 1 (余2) 216 / 2 = 108(余0) 以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数，所以就得出了 434 和 652 的最大公约数 2。

算法的核心其实是 ：$gcd(a,b)=gcd(b,a\mathrm{m}\mathrm{o}\mathrm{d}b)gcd(a,b)\; =\; gcd(b,a\; \backslash bmod\; b)$ （即：$aa$ 和 $bb$ 的最大公约数等于 $aa$ 和 $a\mathrm{\%}ba\backslash \%b$ 的最大公约数。这个性质在本文最后会给出证明） 然后我们考虑，对于两个数 $a\mathrm{、}ba、b$ ， 如果$a\mathrm{\%}b==0a\backslash \%b==0$的话,那这两个数的最大公约数是 $bb$ 这样的话代码我们就可以直接写出来了。

c++

class Solution {
public:
    int gcd(int a, int b) {
        if(a%b==0){return b;}
        else{return gcd(b,a%b);}
    }
};

java

import java.util.*;
public class Solution {
    public int gcd (int a, int b) {
        if(a%b==0){return b;}
        else{return gcd(b,a%b);}
    }
}

python

class Solution:
    def gcd(self , a , b ):
        if a%b==0:
            return b
        else:
            return self.gcd(b,a%b)

$gcd(a,b)=gcd(b,a\mathrm{m}\mathrm{o}\mathrm{d}b)gcd(a,b)\; =\; gcd(b,a\; \backslash bmod\; b)$ 的证明： 我们只需要证明$gcd(a,b)=gcd(b,a-b)gcd(a,b)\; =\; gcd(b,a\; -b)$，就可以满足$gcd(a,b)=gcd(b,a-b)=gcd(b,a-b-b)=gcd(b,a-b\mathrm{.}\mathrm{.}\mathrm{.}-b)=gcd(b,a\mathrm{m}\mathrm{o}\mathrm{d}b)gcd(a,b)\; =\; gcd(b,a\; -b)\; =\; gcd(b,a-b-b)\; =\; gcd(b,a-b...-b)\; =\; gcd(b,a\; \backslash bmod\; b)$ 下面我们来证明$gcd(a,b)=gcd(b,a-b)gcd(a,b)\; =\; gcd(b,a\; -b)$： 设 $gcd(a,b)=cgcd(a,b)=c$ 我们先证明 $cc$ 是 $bb$ 和 $a-ba-b$ 的公约数： 那么$a=k_1\times ca\; =\; k\_1\backslash times\; c$ , $b=k_2\times cb\; =\; k\_2\backslash times\; c$ $a-b=(k_1-k_2)\times ca\; -\; b\; =\; (k\_1-k\_2)\backslash times\; c$ $k_1,k_2,k_3,k_{4}k\_1,k\_2,k\_3,k\_4$ 为正整数 这样就可以推出，$cc$ 是 $bb$ 和 $a-ba-b$ 的公约数

下面我们来证明 $cc$ 是 $bb$ 和 $a-ba-b$ 的最大公约数： 假设 $gcd(b,a-b)gcd(b,a-b)$ 是 $dd$ 不是 $cc$ ，那么 $d>cd>c$ $b=k_3\times db\; =\; k\_3\backslash times\; d$ , $a-b=k_4\times da-b\; =\; k\_4\; \backslash times\; d$ $\Rightarrow a=(k_3+k_4)d\backslash Rightarrow\; a\; =\; (k\_3+k\_4)d$ $\Rightarrow \backslash Rightarrow$ d是a和b的共同因子，但$gcd(a,b)=cgcd(a,b)=c$，则$d\le cd\backslash leq\; c$,与$d>cd>c$矛盾，所以假设不成立，得证$cc$ 是 $bb$ 和 $a-ba-b$ 的最大公约数：