ctyl's problem solving

競技プログラミングが主な話題です。

AGC003 D Anticube

概ね解説と方法は同じですが、自分の方法は少しアプローチが違うので書くことにしました。

問題

agc003.contest.atcoder.jp

概要

正の整数列 {\{s_i\}_{i=1\dots N}}があたえられる。この中から出来る限り多くの整数を選んで、どの2つの要素の積も立方数にならないようにしたい。最大何個まで選べるか。

解法

考察

最初の考察として、 a bの積が立方数になるならば、任意の整数 c, dについて {ac^{3}} {bd^{3}}は立方数になるという性質を考えます。

この性質から、もし a bが同時に選べないならば、 {ac^{3}} bも同時に選べないことがわかります。

ここで、数列の各要素を3乗数で割り切れなくなるまで割ることを考えます。そのとき3乗数で割った数列の中では、ある元 a(\neq 1)と同時に選べない数字は一つしか存在しません。何故なら、 a={p_1}^{m_1}{p_2}^{m_2}\dots{p_k}^{m_k}素因数分解した時、 m_iは必ず1か2になり、 b={p_1}^{3-m_1}{p_2}^{3-m_2}\dots{p_k}^{3-m_k}と一意に定まるからです。逆に bからも aを一意に定めることができ、この2つの整数はペアとして考えることができます。

2以上の数字はかならずそれ自身と異なるペアを持ちますが、1のペアは1なので、特別に処理する必要があります。

3乗数で割った数列のなかで同じ数字はひとまとめにして個数で管理することにすると、次の方針で答えを出すことができます。

  •  a, bがペアのときは、個数が多い方を選び、答えに加算する。
  • 特例として、数列に1が存在するときは、他のどの1ともペアを作ってしまうので、答えに加算するのは1である。
アルゴリズム

まず数列の各要素を3乗数で割り切れなくなるまで割る部分ですが、 10^{10}の3乗根までの素数( 2200くらい)の3乗で割ると間に合います。(素数→整数としてしまうと、TLEします)

次に、各要素のペアを求める部分です。各要素は a={pq^{2}}と書くことができます(ただし、 p,qは相異なる素数の積)。このとき、ペア b b=p^{2}qとなります。まず方針を述べると、 {p, p^{2}} ( q=1)のペアと pq^{2}, p^{2}q ( q>1)のペアに場合分けをして考えます。

 {p, p^{2}} ( q=1)のタイプのペアを見つけたい場合は、各要素について2乗したものが数列の中に存在するかを調べれば良いです。全ての要素について調べると、long longでもオーバーフローしてしまう可能性がありますが、数列を小さい順にソートして、 10^{5}まで調べれば十分です。

 pq^{2}, p^{2}q ( q>1)のタイプのペアを見つける場合は、各要素について素数の2乗でひたすら割って、残った数を2乗し、割った素数と積をとったものが数列の中に存在するかを調べれば良いです。愚直にやると 10^{5}までの素数で割らなければいけないため、少し工夫をします。

 {{p}\lt{q}}として、数列の小さい順にペアを探すことを考えます。すると、 p^{2}qの方が pq^{2}よりも前に探すことになります。この時、ペア pq^{2}が数列に存在するならば p 10^{10}の3乗根を超えることはありません。なぜなら {p}\lt{q}なので、超えてしまうと pq^{2}>10^{10}となってしまうからです。よって、数列の小さい方から 10^{10}の3乗根までの素数の2乗で割ってペアを計算すれば良いです。

時間計算量は K=2200までの素数の個数を Pとすると、素数列挙の前処理で O(KP)、数列のソートで O(N\log N) p, p^{2} タイプのペアの計算で O(N) pq^{2}, p^{2}qタイプのペアの計算は O(PN)となります。 Pは300弱なので、間に合います。

コード

AGC 003 D


コメンタリー:本番は素数列挙せずに解いたため、TLEしてしまった。定数倍と素数列挙分の高速化の意識が足りず、普通に間に合うと思ってしまったが、早くできるところはした方がよさそう。