← 返回题目列表

AtCoder · oidashi_d

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 。


入力例 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}\),则第一个 第二个数字将是一个有理数。
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