最大公因数数gcd模板

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

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

　　（Max代表较大的数，Min代表较小的数）首先我们要明确这两个数是不成倍数关系的，否则直接返回较小的那个数就可以了。既然两个数不成倍数关系，那么Max里就有几个Min，这一部分是Min对的倍数，对于求最大公因数没有什么贡献了，举个例子，34和16,34里有两个16，也就是一个32，这个32对于求最大公因数已经没有贡献了，因为他可以找到的最大因数16不是最大公因数，那么这时候就减掉这个32（34对16取%），用2和16去求，此时直接返回2就可以了。

代码：

#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;
} 

最大公因数数gcd模板

原文：https://www.cnblogs.com/yuelian/p/11198426.html