AT_oidashi_d 幾何問題を書こう

A君设计了一个几何问题，这个问题的答案通常是一个有理数。为了确保在这个问题中答案总是有理数，A君特意进行了一些改动。详细内容如下： > 一个球体的体积为 $v$，现需要通过削去多余的部分来制作一个尽可能大的立方体。求出可以制作的最大立方体的一条边长，再乘以一个实数 $r$ 输出结果。可以确保答案一定是非零的有理数。 A君已经挑选出了 $n$ 个可能的测试用例，即 $v_1, v_2, \ldots, v_n$，但不知道如何选择适当的 $r$ 使得尽可能多的测试用例产生有理数答案。你需要帮助A君选择一个合适的 $r$，使得产生有理数答案的测试用例数量最多。请问最多可以使多少个测试用例的答案是有理数？ ### 输入格式 - 第一行输入一个整数 $n$，表示候选体积的数量。 - 接下来的 $n$ 行，每行输入一个整数，表示体积 $v_i$。 ### 输出格式 在一行中输出答案为有理数的测试用例数量的最大值。请勿忘记输出末尾的换行符。 ### 数据范围与提示 - $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 分。 - 若无额外限制的情况下正确解决，总可能得到 100 分。 有理数是指可以表示为两个整数 $p$ 和非零整数 $q$ 的比值 $\frac{p}{q}$。在A君的问题中，答案不得为 $0$，因此 $r$ 不能为 $0$。 ### 示例 输入： ``` 4 1 1 125 8 ``` 输出： ``` 4 ``` 例如，当 $r = \sqrt[6]{\frac{3\pi^2}{4}}$ 时，所有结果都是有理数。 输入： ``` 3 4 32 1 ``` 输出： ``` 2 ``` 例如，当 $r = \sqrt[6]{3\pi^2}$ 时，第一个和第二个答案是有理数。 输入： ``` 20 90277606625 641956187000 1264908284352 91500888625 5856056872 722220853000 374787639808 1264908284352 220190972141 1264908284352 46848454976 533633182461 251078438387 5856056872 732007109000 158113535544 19764191943 1247997633984 974301462079 46848454976 ``` 输出： ``` 15 ``` **本翻译由 AI 自动生成**

无

无