アルゴリズム実装と最適化テクニック
問題B：完全立方数を避ける数列選択
数列 $\{a_n\}$ から部分集合を選び、任意の2要素の積が完全立方数とならないようにする。$n\le 10^5$、$1\le a_i\le 10^{10}$。
重要な観察：$10^5$ より大きい素因数を持つ数は常に解答に寄与する。その他の数については、非1の完全立方因子をすべて除去してから処理する。
ll factorizeRandom(ll val) {
if (val % 2 == 0) re ...
5月19日 21:29 投稿