通过分解质因数求若干个数的最小公倍数

求最小公倍数的常规方法回顾

暴力枚举法

long long work(long long a,long long b)
{for(long long i=max(a,b);;i++)if(i%a==0&&i%b==0)return i;
}

大数翻倍法

long long work(long long a,long long b)
{if(a<b) swap(a,b);for(long long i=a;;i+=a) // i 是 a 的倍数，每次增加一倍，i 必然是 a 的倍数，我们只要保证 i 也是 b 的倍数，那么 i 就一定是 a,b 的最小公倍数if(i%b==0)return i;
}

公式法

long long work(long long a,long long b)
{long long c = __gcd(a,b); // 先求 a,b 的最大公约数return a*b/c; //按照公式算出最小公倍数
}

分解质因数求若干个数的最小公倍数

有n个数a[i](i从1到n),求它们的最小公倍数可以采用下面方法：

1. 求出 max(a[i]​)，算出 小于等于 max(a[i]​) 的所有质数 bjbj​

2. 对每一个a[i]进行质因数分解，进而得到 c[i] c[j]其含义为对a[i]分解质因数，能分解出c[i] c[j] 个质因数b[j]。

下面，我们举一个例子，假设我们要求 2 到 15 的最小公倍数。 

• 2,4,6,8,10,12,14 都能分解出质因数 2 ，最多能分解出 3 个（8 分解出 3 个 2），所以，最少公倍数一定包含 3 个质因数 2 （不可能小于 3 个，否则就不可能是 8 的倍数；也不可能多于 3 个，否则就不是最小的倍数）

• 3,6,9,12,15 都能分解出质因数 3，最多能分解出 2 个 3（9 分解出 2 个 3），所以，最少公倍数一定包含 2 个质因数 3

• 5,10,15 都能分解出质因数 5，均只能分解出 1 个 5，所以，最少公倍数一定包含 1 个质因数 5

.....

通过分解质因数的方法求最小公倍数的应用场景

有一些题目并不需要真正输出最小公倍数的具体数值是什么。只需要根据这个分解情况进行下一步计算，分解法在这个时候特别有意义。

公式法中出现除的运算。意味着，中间答案可能会很大，容易溢出。另外，因为有除法的出现，就导致了同余定理不能使用。用分解法来求质因数，最终结果就是对很多很多个质因数乘起来，乘法和加法都是可以运用同余定理的。