gcd 最大公约数

求两的数的最大公约数有以下代码：

#include<algorithm>  
#include<iostream>  
using namespace std;  
  
long long gcd(long long a,long long b)  
{  
    return b==0 ? a : gcd(b,a%b);  
}  
  
int main()  
{  
    int x=12,y=24;  
    cin>>x>>y;  
    int num_gcd=gcd(x,y); //或者直接调用 __gcd(x,y);  
    int num_lcm=x*y/num_gcd; //有 lcm(x,y)*gcd(x,y)=x*y;  
    cout<<num_gcd<<" "<<num_lcm<<"\n";  
}

证明

#

证明辗转相除法就是证明如下关系：
gcd(a, b) = gcd(b, a % b)
假设a % b = r，即需要证明的关系为：gcd(a, b) = gcd(b, r)
证明过程：

因为a % b = r，所以如下两个等式必然成立
a = b * q + r，q为0、1、2、3….中的一个整数
r = a − b * q，q为0、1、2、3….中的一个整数

假设u是a和b的公因子，则有: a = s * u, b = t * u
把a和b带入2)得到，r = s * u - t * u * q = (s - t * q) * u
这说明 : u如果是a和b的公因子，那么u也是r的因子
假设v是b和r的公因子，则有: b = x * v, r = y * v
把b和r带入1)得到，a = x * v * q + y * v = (x * q + y) * v
这说明 : v如果是b和r的公因子，那么v也是a的公因子
综上，a和b的每一个公因子 也是 b和r的一个公因子，反之亦然
所以，a和b的全体公因子集合 = b和r的全体公因子集合
即gcd(a, b) = gcd(b, r)
证明结束

lcm

#

最小公倍数即 (a*b)/gcd(a,b)