AGC003 D Anticube
概ね解説と方法は同じですが、自分の方法は少しアプローチが違うので書くことにしました。
問題
概要
正の整数列があたえられる。この中から出来る限り多くの整数を選んで、どの2つの要素の積も立方数にならないようにしたい。最大何個まで選べるか。
解法
考察
最初の考察として、との積が立方数になるならば、任意の整数についてとは立方数になるという性質を考えます。
この性質から、もしとが同時に選べないならば、とも同時に選べないことがわかります。
ここで、数列の各要素を3乗数で割り切れなくなるまで割ることを考えます。そのとき3乗数で割った数列の中では、ある元と同時に選べない数字は一つしか存在しません。何故なら、と素因数分解した時、は必ず1か2になり、と一意に定まるからです。逆にからもを一意に定めることができ、この2つの整数はペアとして考えることができます。
2以上の数字はかならずそれ自身と異なるペアを持ちますが、1のペアは1なので、特別に処理する必要があります。
3乗数で割った数列のなかで同じ数字はひとまとめにして個数で管理することにすると、次の方針で答えを出すことができます。
- がペアのときは、個数が多い方を選び、答えに加算する。
- 特例として、数列に1が存在するときは、他のどの1ともペアを作ってしまうので、答えに加算するのは1である。
アルゴリズム
まず数列の各要素を3乗数で割り切れなくなるまで割る部分ですが、の3乗根までの素数(くらい)の3乗で割ると間に合います。(素数→整数としてしまうと、TLEします)
次に、各要素のペアを求める部分です。各要素はと書くことができます(ただし、は相異なる素数の積)。このとき、ペアはとなります。まず方針を述べると、 ()のペアと ()のペアに場合分けをして考えます。
()のタイプのペアを見つけたい場合は、各要素について2乗したものが数列の中に存在するかを調べれば良いです。全ての要素について調べると、long longでもオーバーフローしてしまう可能性がありますが、数列を小さい順にソートして、まで調べれば十分です。
()のタイプのペアを見つける場合は、各要素について素数の2乗でひたすら割って、残った数を2乗し、割った素数と積をとったものが数列の中に存在するかを調べれば良いです。愚直にやるとまでの素数で割らなければいけないため、少し工夫をします。
として、数列の小さい順にペアを探すことを考えます。すると、の方がよりも前に探すことになります。この時、ペアが数列に存在するならばはの3乗根を超えることはありません。なぜならなので、超えてしまうととなってしまうからです。よって、数列の小さい方からの3乗根までの素数の2乗で割ってペアを計算すれば良いです。
時間計算量はまでの素数の個数をとすると、素数列挙の前処理で、数列のソートで、 タイプのペアの計算で、タイプのペアの計算はとなります。は300弱なので、間に合います。
コード
コメンタリー:本番は素数列挙せずに解いたため、TLEしてしまった。定数倍と素数列挙分の高速化の意識が足りず、普通に間に合うと思ってしまったが、早くできるところはした方がよさそう。