辗转相除法 - 求解最小公倍数和最大公约数

辗转相除法

欧几里得算法又称辗转相除法，是指用于计算两个非负整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。

其计算原理依赖于下面的定理： 定理：两个整数的最大公约数等于其中较小的那个数和两数相除余数的最大公约数。最大公约数（Greatest Common Divisor）缩写为GCD。

gcd(a,b) = gcd(b,a mod b) (不妨设a>b 且r=a mod b ,r不为0)

证法一 a可以表示成a = kb + r（a，b，k，r皆为正整数，且r 假设d是a,b的一个公约数，记作d|a,d|b，即a和b都可以被d整除。 而r = a - kb，两边同时除以d，r/d=a/d-kb/d，由等式右边可知m=r/d为整数，因此d|r 因此d也是b,a mod b的公约数。 因(a,b)和(b,a mod b)的公约数相等，则其最大公约数也相等，得证。

证法二 假设c = gcd(a,b),则存在m,n，使a = mc, b = nc; 令r = a mod b，即存在k，使r = a-kb = mc - knc = (m-kn)c; 故gcd(b,a mod b) = gcd(b,r) = gcd(nc,(m-kn)c) = gcd(n,m-kn)c; 则c为b与a mod b的公约数; 假设d = gcd(n,m-kn), 则存在x,y, 使n = xd, m-kn = yd; 故m = yd+kn = yd+kxd = (y+kx)d; 故有a = mc = (y+kx)dc, b = nc = xdc; 可得 gcd(a,b) = gcd((y+kx)dc,xdc) = dc; 由于gcd(a,b) = c, 故d = 1; 即gcd(n,m-kn) = 1, 故可得gcd(b,a mod b) = c; 故得证gcd(a,b) = gcd(b,a mod b).

注意:两种方法是有区别的。

最大公约数和最小公倍数

如果已知两个数A和B的最大公约数为m，那么最小公倍数n = （A*B)/m;

代码

#include<iostream>

using namespace std;

//求解最大公约数
int func(int x,int y){
          
   
    int z = min(x,y);
    while(x % y != 0){
          
   
        z = x%y;
        x = y;
        y = z;
    }
    return z;
}

int main(){
          
   
    int x,y;
    cin >> x >> y;
    //输出最大公倍数
    cout << x * y / func(x,y) << endl;
    return 0;
}