AT_oidashi_d 幾何問題を書こう

[problemUrl]: https://atcoder.jp/contests/oidashi/tasks/oidashi_d 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 $ としてはいけない。 ``` 4 1 1 125 8 ``` ``` 4 ``` 例えば\\(r=\\sqrt\[6\]{\\frac{3\\pi^2}{4}}\\)とすると、どれも有理数になります。 rの値を修正しました。(17:14) ``` 3 4 32 1 ``` ``` 2 ``` 例えば\\(r=\\sqrt\[6\]{3\\pi^2}\\)とすると、1番目と 2番めが有理数になります。 rの値を修正しました。(17:14) ``` 20 90277606625 641956187000 1264908284352 91500888625 5856056872 722220853000 374787639808 1264908284352 220190972141 1264908284352 46848454976 533633182461 251078438387 5856056872 732007109000 158113535544 19764191943 1247997633984 974301462079 46848454976 ``` ``` 15 ```

N/A

N/A