← 返回题目列表

AtCoder · abc413_d

G. 制作几何序列

中文机器翻译题面 查看原题


分数: 425 点

问题陈述

给你一个整数序列 A=(A_1,A_2,\ldots,A_N) 长度 N。 保证对于任意 i\ (1\le i\le N), A_i 不是 0.

判断是否存在排列 B=(B_1,B_2,\ldots,B_N) of A 这样 B 形成一个几何序列。

一个序列 如果存在实数, S=(S_1,S_2,\ldots,S_N) 是等比数列 r 这样 S_{i+1}=rS_i 对于所有整数 1\le i\lt N.

解决 T 每个输入文件的测试用例。

约束

  • 1\le T\le10^5
  • 2\le N\le2\times10^5
  • -10^9\le A_i\le10^9\ (1\le i\le N)
  • A_i\ne0\ (1\le i\le N)
  • 总和 N 单个输入文件中的所有测试用例最多 2\times10^5.
  • 所有输入值均为整数。

输入

输入由标准输入给出,格式如下:

T
\mathrm{testcase}_1
\mathrm{testcase}_2
\vdots
\mathrm{testcase}_T

其中 \mathrm{testcase}_i 是 i- 第一个测试用例 (1\le i\le T),每个测试用例按以下格式给出:

N
A_1 A_2 \ldots A_N

输出

输出 T 行。 的 i第行 (1\le i\le T) 应包含 Yes if A 可以重新排列以形成几何序列 i- 第一个测试用例,以及 No 否则。


示例输入 1

3
5
1 8 2 4 16
5
-16 24 54 81 -36
7
90000 8100 -27000 729 -300000 -2430 1000000

示例输出 1

Yes
No
Yes

在第一个测试用例中,重新排列 (16,8,4,2,1) of A 形成具有公比的等比数列 r=\frac{1}{2}。 因此,打印 Yes 在第一行。

在第二个测试用例中,没有重新排列 A 满足条件。 因此,打印 No 在第二行。