E - Many LCMs
在本题中，需要处理 \(n\le 2e5\) 个 \(A_{i}\) 的所有不同质因子集合（不需要求个数），其中 \(A_{i}\le 10^{7}\)。显然每个 \(A_{i}\) 最多只有 \(8\) 种不同的质因子，但是直接按照质因数分解的方式来写是 \(O(n\sqrt A_{i})\) 的；若通过线性筛质数+调和级数预处理 \(1\backsim 10^{7}\) 每个数的质因子，复杂度为这些数的质因子种类数之和，\(< 8 \times 10^{7}\)，理论上是可行的，但这样做的常数太大，也并不合适。
这里记录一种线性做法：首先在线性筛质数的过程中，可以得到 \(1 \backsim 10^{7}\) 每个数的最小质因子。因为线性筛质数就是利用了 “每个数只能被其最小质因子筛一次” 这个原理保证了线性复杂度。那么在筛的时候，就可以顺带着记录每个数是被哪个质因子筛掉的，该质因子就是这个数的最小质因子。
bool st[10000005];
int primes[10000005], tot;
int minp[10000005]; // minp[x]：x 含有的最小质因子
void sieve(int n){for(int i = 2; i <= n; i ++){if(!st[i]) primes[++tot] = i, minp[i] = i;for(int j = 1; j <= tot && primes[j] <= n / i; j ++){st[i * primes[j]] = true; // i * primes[j] 被最小质因子 primes[j] 筛掉minp[i * primes[j]] = primes[j];if(i % primes[j] == 0) break;}}
}
得到了 \(minp[1\backsim 10^{7}]\) 后，对于每个 \(A_{i}\)，我们可以得到 \(A_{i}\) 的最小质因子 \(x = minp[A_{i}]\)；通过将 \(A_{i}\) 不断除以 \(x\)，我们会消除掉所有的质因子 \(x\)。此时 \(A_{i}\) 变为了 \(A_{i}'\)，接下来我们又可以通过 \(x = minp[A_{i}']\) 得到 \(A_{i}'\) 的最小质因子，然后再进行类似操作，最终就可以以 \(O(\log A_{i})\) （因为 \(A_{i}\) 的质因子的个数就是 \(O(\log{A_{i}})\) 级别）的复杂度得到 \(A_{i}\) 的所有质因子以及每种质因子的数量，总复杂度 \(O(A + n\log A)\)（因为还有一个关于值域线性筛的过程，可见这种方法适用于 \(A_{i} \le 10^{7}\) 的情况，但不适用于 \(10^{9}\)），是非常小的。
for(int i = 1; i <= n; i ++){int x = a[i];while(x > 1){int p = minp[x];int cnt = 0;while(x % p == 0){cnt ++;x /= p;}// 记录信息 (p, cnt)}
}
code