最大公因数数gcd模板

　　首先蒟蒻是在大佬的博客里学习的代码，代码风格多有相似之处，大佬博客https://www.cnblogs.com/lMonster81/p/10433902.html

最大公因数那，顾名思义就是两个数共有的因数里最大的那个，辗转相除求最大公因数所用的原理就是两个数的最大公因数等于这两个数中【较小的那个数】和【两数之差】的最大公因数，证明如下：

　　

　描述：关于辗转相除法的具体实现在这里就不具体说明了，本文要记录的是辗转相除法应用于求最大公约数的算法证明过程。

　　假设：

求m和n的最大公约数。
a,b分别是m除以n的商和余数，即m=na+b。
gcd(m,n)表示m和n的最大公约数。
　　求证：gcd(m,n)=gcd(n,b)

　　证明：

　　　　设c=gcd(m,n), d=gcd(n,b)

　　1.　∵c为m和n的公约数

　　　　∴m能被c整除，n也能被c整除

　　　　∴na也能被c整除  参照推论一

　　　　∴m-na也能被c整除(即b能c整除)  参照推论二

　　　　∴c为n和b的公约数

　　　　∵d为n和b的最大公约数

　　　　∴c≤d

　　2.　同理可证 d≤c

　　　　∵d为n和b的公约数

　　　　∴n能被d整除，b也能被d整除

　　　　∴na也能被d整除  参照推论一

　　　　∴na+b也能被d整除(即m能d整除)  参照推论二

　　　　∴d为m和n的公约数

　　　　∵c为m和n的最大公约数

　　　　∴d≤c

　　综上所述：c=d，即gcd(m,n)=gcd(n,r)

 

        推论一：若a能被b整除(a=tb)，则如果k为正整数，则ka也能被b整除(ka=ktb)。

        推论二：若a能被c整除，b也能被c整除，则(a±b)也能被c整除。

　　以上证明转载自：https://www.cnblogs.com/zwffff/archive/2010/08/25/1808178.html

代码：

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int a,b;
int gcd(int x,int y)
{
    int Max=max(x,y),Min=min(x,y);
    return Max%Min==0?Min:gcd(Max,Max%Min);
}
int main()
{
    cin>>a>>b;
    int c=gcd(a,b);
    cout<<c;
    return 0;
} 

 关于最大公因数与最小公倍数的其他几个知识：

　　1,：最大公因数与最小公倍数的乘积等于原两个数的乘积。