Codeforces Round 1060 (Div. 2)

 ABDの三完。Cが分からなかった。

コンテストへのリンク

コンテスト後のツイート

Codeforces Round 1060 (Div. 2) ABD。Cが分からず。何？
A 言われた通りに左から決めるだけだがちょっと難読。
B 最初に操作1を全部やってしまう。
C 素数列挙or約数列挙せずに解く方法あるの？
D 木は二部グラフ。ゴールからの距離が遠いところから消していく。

— titia (@titia_til) October 19, 2025

C2. No Cost Too Great (Hard Version)

　C1の時点で分からなかったのですが。

　他の方のACコードや、maspyさんの解説などを参考にしてAC。コンテスト中の考察は普ちゃんと間違っており、結構難しい問題に感じてしまった。

　コンテスト中は、A[i]たちの素因数の個数*nくらいの計算量が必要な気がしてしまったが、それはさすがに間に合わない。

　Bをソートしたとき（SBとする）、SB[0]+SB[1]が明らかに答えになるので、これより小さくなる可能性があるものを探せば良いと考えると、SB[0]に対応するindex以外は、０回か1回足すことしか考えなくて良い。

　そうすると、他の素数たち全てを見る必要はなく、A[ind]の素因数が、「A[i]の素因数たち(i=indを除く)の集合」に含まれるかどうかさえあれば良いので、setを使って判定できる。

　これでC1は解ける。

　SB[0]に対応するindexについては「A[i]の素因数たち(i=indを除く)の集合」全てに対して計算を行えば、C2も解ける。