GCD（最大公约数）和LCM（最大公倍数）都是大家很熟悉的东西，这里不再赘述基本概念，而是浅谈一下GCD和LCM所具有的一些性质。

算数基本定理

任何一个大于1的自然数 N,如果N不为质数，那么N可以唯一分解成有限个质数的乘积$N=P_{1}^{a_{1}}P_{2}^{a_{2}}P_{3}^{a_{3}}……P_{n}^{a_{n}}$，这里$P_{1}<P_{2}<P_{3}……<P_{n}$均为质数，其中指数$a_{i}$是正整数。

特别的对于$N = 1$的时候显然有$1 = 1 \cdot P_{1}^{0}P_{2}^{0}P_{3}^{0}……P_{n}^{0}$，不妨看作是任意质数的0次幂的乘积，对于N属于质数的时候显然有$N = N^{1}$

质因数分解

由算数基本定理我们就可以很容易得到质因数分解的算法，即从2开始逐个枚举质因数，因为质因数的幂次可能会大于1所有我们就对数N一直除到不能被整除为止，继续枚举下一个质因数

vector<int> factor;
void factorization(int x){
    int k = 2;
    while(x > 1){
        if(x % k == 0){
            factor.push_back(k);
            x /= k;
        }else k++;
    }
}

算法的平均时间复杂度为$O(n^{\frac{1}{4}})$，细心的同学可能一眼就看到了一种比较极端的情况，也就是N本身就为质数的情况，这种情况下复杂度显然是$O(n)$，所有很多时候我们需要先对$N$判断一下是否是质数。

重新认识GCD

假设有数$a$和数$b$，其中

$a = P_{1}^{1}P_{2}^{2}P_{3}^{2}$

$b = P_{2}^{1}P_{3}^{2}P_{4}^{1}$

此时我们并不关心a和b具体是多少，能同时整除$a$和$b$的的数显然是$a$或者$b$中的一些质因数的乘积，$a$和$b$最多的共同的质因数是$P_{2}^{1}P_{3}^{2}$，对$a$和$b$同时除以$P_{2}^{1}P_{3}^{2}$之后显然没有共同质因数了，那么我们就得到了最大公约数为$P_{2}^{1}P_{3}^{2}$

$lcm$就是共同质因数和不同质因数的乘积，其中共同质因数中每个质因数的次数取次数较高的那个一，$lcm(a, b) = P_{1}^{1}P_{2}^{2}P_{3}^{2}P_{4}^{1}$

这也从一个很好的角度解释了为什么$lcm(a,b) = a \cdot b / gcd(a, b)$

读者可以自己去验证一下结论的正确性，对于 这一性质有很多的妙用，读者可以自行思考。