Description
給你 $N$ 個數字，對於每個數字你可以進行至多一次操作：將 $a_i$ 除以一個他小於等於 $k$ 的因數。
每個數字 $a_i$ 有各自的 $e_i$ 代表若對他採取操作會需要增加的費用。
總花費 = 操作次數 $\cdot$ 費用和，而你的目標是在最小花費下讓所有數字的 GCD 變成 $1$
輸出達成目標的最小總花費，無法達成的話輸出 $-1$。
($N \leq 10^6$ 、 $a_i, k \leq 10^{12}$ 、 $e_i \leq 10^9$)
Solution
題目看起來很 dp，只是狀態感覺頗難列，複雜度也非常差，因此還要再多一些觀察。
首先我們先找到一開始的 GCD，若為 $0$ 則直接輸出答案，否則對他做質因數分解，假設其有 $m$ 個質因數，由於 GCD $\leq 10^{12}$，$m$ 至多為 $11$。
第一個觀察：若目標是可以達成的，我們最差只需要對 $m$ 個質因數各自進行操作就能達成目標。
由於 $m$ 至多為 $11$，可能就會聯想到用 bitmask(?)
的確，「讓 GCD 不包含 mask 之質因數的最小花費」可以作為其中一維狀態，而想到這邊的同時應該也會發現還有一維必須是操作次數。
我們讓 mask 代表對 $a_i$ 進行一次操作可以拔掉的質因數：
$$dp[i][j] = dp[i - mask][j-1] + cost[a_i]$$
透過預處理我們可以對於每個 mask 先找到 $e_i$ 前 $m$ 小的 $a_i$，並用其來進行 dp 狀態轉移。
預處理複雜度 $O(N \cdot 2^m \cdot m)$，dp複雜度 $O(3^m \cdot m^2)$，因此目前複雜度為 $O(N \cdot 2^m \cdot m + 3^m \cdot m^2)$，TLE。
第二個觀察：我們不用在乎那些沒有出現在 GCD 裡的質數，可以直接將他從 $a_i$ 除掉。
這麽做以後會發現出現非常多重複的數字，根據前面的觀察，對於每種重複的數字我們只需要取出 $e_i$ 最小的前 $m$ 個就好。
估計或感覺一下，就會猜 $N$ 應該變小很多，確切來說，現在只會剩下至多 $M = 12000$ 個數字。
複雜度變為 $O(M \cdot 2^m \cdot m + 3^m \cdot m^2) \approx 10^8$，成功 AC。