Prime Collector

解説

この問題は「クエスト」「素因数」を頂点として「クエストを受注、クリアして素因数を貰う」を辺としたグラフにおける最小辺被覆問題に帰着することができます。$2 \leq A_i$ という制約により、このグラフには孤立点がないため次式が成立します。

• $|最小辺被覆| = |頂点数| - |最大マッチング|$

このグラフは二部グラフになるため最大マッチングは最大流問題に帰着することができ（二部マッチング）、頂点数・辺数をそれぞれ $n, m$ とおくと、Dinic 法を用いることで計算量 $O(\sqrt{n}m)$ で解くことができます。各クエストの素因数を求める前計算を加えると全体では $O(N \sqrt{\mathrm{max}\{A_i\}} + \sqrt{n}m)$ となり、以上により最小辺被覆が求まります。

最小辺被覆を知らなかったとしても「二部マッチングを構築してから、余った頂点を一つずつ加えていけば最適になりそう」という考えに至れば解くことは可能です（これは最小辺被覆の構築手順そのものです）。

ちなみに、最小辺被覆は蟻本にも「最小辺カバー」として紹介されています。

計算量解析

（Dinic 法の計算量の詳細については下部の参考リンクをご確認ください）

頂点数と辺数をそれぞれ $n, m$ とおくと、一般に Dinic 法の計算量は $O(n^2m)$ となりますが、二部マッチングの場合は辺の容量がすべて $1$ であるため $O(\sqrt{n}m)$ にまで改善され、$O(\mathrm{min}(n^{\frac{2}{3}}, m^{\frac{1}{2}})m)$ という評価をすることもできます。

次に、本問での頂点数 $n$ と辺数 $m$ の個数について述べます。

$10^6$ 以下の素数は全部で $78498$ 個ありますが、$N \leq 10^4$ の制約であるため、登場する素因数の種類数の最大は $N$ 程度となります（後述する整数などによって "素因数の種類数を稼ぐ" ことは可能ですが、そのような整数はほとんど作れないことが分かります）。よって、頂点数 $n$ の最大数は $2N$ 程度と見積もれます。

一方、$A_i \leq 10^6$ の制約において $A_i$ が持つ素因数の最大数は、下記ケースを考えることで $7$ 個であると分かります。よって、辺数 $m$ の最大数は $8N$ 程度と見積もれます（source と sink に張られる辺も含まれることに注意）。

• $2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510 < 10^6$

以上により、最大流の計算量は $n = 2N, m = 8N$ のときが最悪ケースとなりますが、$\sqrt{n}m \sim 1.1 \times 10^7$ 程度であるため間に合います（$n, m$ の最悪ケースが両立するテストケースは作れないため、実際の計算量はもう少し小さくなります）。

参考

• [1] 実世界で超頻出！二部マッチング (輸送問題、ネットワークフロー問題）の解法を総整理！‬

• [2] 二部グラフの最小点被覆、最大安定集合 (最大独立集合)、最小辺被覆を総整理！

• [3] Dinic 法

• [4] Dinic 法とその時間計算量

解答例

解答例では「素因数に番号を振る処理」に連想配列を用いていますが、制約が $A_i \leq 10^6$ であることから、長さ $\mathrm{max}\{A_i\}$ の配列を代わりに用いて素因数の番号を管理する実装も可能です。

また、高速素因数分解を用いることで素因数分解パートを高速化することができます。最大流パートも同程度の計算量であるため全体では定数倍高速化となります。