质因数分解与 LCM 计算

最小公倍数（LCM）是指一组数中能够被每个数整除的最小的正整数。

常见求 LCM 方法是先利用辗转相除法求出两数的最大公因数 GCD(a,b)，然后求 LCM(a,b) = a * b / GCD(a,b)，但对于本题来说，LCM出现的值可能远远超出 long long 的范围，分析如下：

题目的范围：$100\mathrm{\%}：n<=100,a_i<=10000$，数据极限是 $100$ 个整数，而这 $100$ 个数据都刚好互质，范围会多大我们无法计算，但一定非常大，最终不会超过 ${10000}^{100}$ 。

随意的假设几个数：9997 99995 99994 99993 99991 ，这几个数看起来是互质的，至于实际是否互质，不重要，这几个相乘就超过了 long long 类型。

这时候会想到高精度，这原则上是可行的，但这道题并没有让我们求解这个最小公倍数的准确值，只是让我们求出它的质因数分解，这时候要用到以下的一个规律：

📌 LCM 等于各个质因数的最高次幂相乘

为什么 LCM 是各个质因数的最大指数的乘积？

最小公倍数的定义要求找出一个数，它能同时被所有输入的数整除。为了满足这个条件，我们需要考虑每个质因子在所有数中出现的次数，选取每个质因子的最大指数。

例子说明：

假设我们有以下三个数：

• $a=12=2^2\times 3^1$
• $b=18=2^1\times 3^2$
• $c=30=2^1\times 3^1\times 5^1$

我们需要计算 $a$, $b$, 和 $c$ 的最小公倍数（LCM）。

1. 质因数分析：

   • 对于质因子 $2$，数 $a$ 提供 $2^2$，数 $b$ 提供 $2^1$，数 $c$ 提供 $2^1$。要同时满足三个条件才能整除，选择最大指数，即 $2^2$。
   • 对于质因子 $3$，数 $a$ 提供 $3^1$，数 $b$ 提供 $3^2$，数 $c$ 提供 $3^1$。需要选择最大指数，即 $3^2$。
   • 对于质因子 $5$，只有 $c$ 提供了质因子 $5$，并且是 $5^1$，因此需要 $5^1$。

2. LCM 计算： LCM 是所有质因子中最高次数的乘积：

   $$\text{LCM}(a,b,c)=2^2\times 3^2\times 5^1=4\times 9\times 5=180$$

因此，$a=12$, $b=18$, 和 $c=30$ 的最小公倍数是 $180$。

为什么选取最大指数？

• 整除条件：对于任何两个数 $x$ 和 $y$，如果 $x$ 可以整除 $y$，那么 $x$ 中每个质因子的指数必须小于等于 $y$ 中对应质因子的指数。因此，为了确保 LCM 能被每个输入数整除，我们需要选择每个质因子在所有数中的最大指数。
• 最小公倍数的定义：最小公倍数是一个能被所有输入数整除的最小数。如果我们选择的某个质因子的指数小于其最大值，它就可能导致 LCM 无法满足“被所有数整除”的要求。因此，必须选取每个质因子的最大指数，确保 LCM 能同时整除所有输入数。

总结：

最小公倍数是通过选择每个质因子的最大指数来计算的，因为：

1. 只有当某个数的质因子的指数足够大时，才能确保该数能够被所有其他数整除。
2. 选择每个质因子的最大指数，保证了 LCM 是能够整除所有输入数的最小值。

通过质因数分解并选择最大指数，我们能够高效地计算出多个数的最小公倍数。