D - 幾何問題を書こう Editorial /

Time Limit: 2 sec / Memory Limit: 291 MB

問題文

A君は、答えが無理数になりうる幾何問題を作りました。 答えが有理数であれば誤差が出ないように出力できることを学んだA君は、 答えが必ず有理数になるように工夫して、次のような問題にしました。 

体積が v の球を手に入れた。この球を削ってできるだけ大きな立方体を作りたい。
削り出せる立方体のうち、一番大きいものの一辺の長さを r 倍して答えよ。

答えはは必ず 0 でない有理数になることが保証されている。

A君はすでにこの問題のテストケースとして使う v の候補を n 個決めましたが、 困ったことに、実数 r をどう決めれば答えが有理数になるのかが分かりません。 そこで、あなたはA君にテストケース候補 v_1,...,v_n を見せてもらい、 答えが有理数になるテストケースができるだけ多くなるように 実数 r を決めてあげることにしました。 うまく実数 r を決めると、最大でいくつのテストケースを使うことができるでしょうか？

入力

入力は以下の形式で標準入力から与えられる。 
n
v_1
... 
v_n
  • n,v_i は整数
  • 1 \leq n \leq 30000
  • 1 \leq v_i \leq 10^{12} (1 \leq i \leq n)

出力

答えが有理数になるテストケース数の最大を一行に出力してください。出力の末尾には改行を入れること。

部分点

この問題には部分点が設定されている。
  • n\leq 2000 かつ v_i\leq 10^6 であるデータセットに 正解した場合、98点が得られる。
  • 追加制約のないデータセットに正解した場合さらに 2 点が得られ合計 100 点が得られる。

注意

有理数とは、整数 p と 0 でない整数 q を使って \(\frac{p}{q}\) と表せる数のことである。
A君の問題では、答えが 0 にならないことを保証したいので、 r は 0 としてはいけない。

入力例 1

4
1
1
125
8

出力例 1

4

例えば\(r=\sqrt[6]{\frac{3\pi^2}{4}}\)とすると、どれも有理数になります。
rの値を修正しました。(17:14)

入力例 2

3
4
32
1

出力例 2

2

例えば\(r=\sqrt[6]{3\pi^2}\)とすると、1番目と 2番めが有理数になります。
rの値を修正しました。(17:14)

入力例 3

20
90277606625
641956187000
1264908284352
91500888625
5856056872
722220853000
374787639808
1264908284352
220190972141
1264908284352
46848454976
533633182461
251078438387
5856056872
732007109000
158113535544
19764191943
1247997633984
974301462079
46848454976

出力例 3

15