CF Round #868 (Div.2) C. Strongly Composite (贪心 + 构造 + 质因数分解)

题意：给定一个数组a，构造一个数组b，数组b尽可能长，且数组b里全是强合数，并且a数组所有数相乘等于b数组所有数相乘；并且 b 的长度要尽可能大

强合数：如果一个数的质因子的个数小于等于合数的个数，那么这个数就是强合数。

思路: 我们要让数组b的乘积对于数组a的乘积, 因此我们可以对数组 a 里面的每一个数进行质因数分解.

在此之前, 我们先"手玩"一下题目中的强合数, 看看强合数满足什么性质:

假设 x 是一个任意整数, 我们可以对其进行质因子分解:

假设所有因子的个数为 D，,第 i 个质因数的幂为 di,  那么根据排列组合有:

假设所有因子中有 m 个质数, 那么合数为 D - m - 1, 根据强合数的定义 m 要满足一下条件:

也就是说:

对于每一个 di，我们知道 , 那么 , 因此我们可以得到一个更强的条件:

显然当 m = 3, 4, ..., 时都是成立的。

当 m = 1 时, 如果要满足强合数, 那么 d1 >= 2

当 m = 2 时, 如果要满足强合数, 那么 max(d1, d2) >= 2

当 m = 3, 4, ... 时, 我们一定能构造出强合数

我们要让数组 b 尽可能大, 对于 m = 2 时包含了 m = 1 时的条件, 所以我们肯定不会选择 m = 2 (因为可以使用更少的质因子), 而选择 m = 3, 因此贪心的策略是:

先找出所有两个相同的质因子并构造出一个强合数。找完后剩余的就找出 3 个不同的质因数构造出一个强合数。其余的质因子和合数可以放到前面构造的组里不影响答案。