題意：給定一個數(shù)組a，構(gòu)造一個數(shù)組b，數(shù)組b盡可能長，且數(shù)組b里全是強合數(shù)，并且a數(shù)組所有數(shù)相乘等于b數(shù)組所有數(shù)相乘；并且 b 的長度要盡可能大

強合數(shù)：如果一個數(shù)的質(zhì)因子的個數(shù)小于等于合數(shù)的個數(shù)，那么這個數(shù)就是強合數(shù)。

思路:?我們要讓數(shù)組b的乘積對于數(shù)組a的乘積, 因此我們可以對數(shù)組 a 里面的每一個數(shù)進(jìn)行質(zhì)因數(shù)分解.

在此之前, 我們先"手玩"一下題目中的強合數(shù), 看看強合數(shù)滿足什么性質(zhì):

假設(shè) x 是一個任意整數(shù), 我們可以對其進(jìn)行質(zhì)因子分解:

假設(shè)所有因子的個數(shù)為 D，,第 i 個質(zhì)因數(shù)的冪為 di,? 那么根據(jù)排列組合有:

假設(shè)所有因子中有 m 個質(zhì)數(shù), 那么合數(shù)為 D - m - 1, 根據(jù)強合數(shù)的定義 m 要滿足一下條件:

也就是說:

對于每一個 di，我們知道?, 那么?, 因此我們可以得到一個更強的條件:

顯然當(dāng) m = 3, 4, ..., 時都是成立的。

當(dāng) m = 1 時, 如果要滿足強合數(shù), 那么 d1 >= 2

當(dāng) m = 2 時, 如果要滿足強合數(shù), 那么 max(d1, d2) >= 2

當(dāng) m = 3, 4, ... 時, 我們一定能構(gòu)造出強合數(shù)

我們要讓數(shù)組 b 盡可能大,?對于 m = 2 時包含了 m = 1 時的條件,?所以我們肯定不會選擇 m = 2 (因為可以使用更少的質(zhì)因子), 而選擇 m = 3, 因此貪心的策略是:

先找出所有兩個相同的質(zhì)因子并構(gòu)造出一個強合數(shù)。找完后剩余的就找出 3 個不同的質(zhì)因數(shù)構(gòu)造出一個強合數(shù)。其余的質(zhì)因子和合數(shù)可以放到前面構(gòu)造的組里不影響答案。