/ 
Time Limit: 2 sec / Memory Limit: 1024 MiB
配点 : 425 点
問題文
長さ N の整数列 A=(A _ 1,A _ 2,\ldots,A _ N) が与えられます。 ここで、どの i\ (1\le i\le N) についても A _ i が 0 でないことが保証されます。
A を適切に並べ替えた数列 B=(B _ 1,B _ 2,\ldots,B _ N) が等比数列になることがあるか判定してください。
ただし、数列 S=(S _ 1,S _ 2,\ldots,S _ N) が等比数列であるとは、ある実数 r が存在してすべての整数 1\le i\lt N に対して S _ {i+1}=rS _ i が成り立つことをいいます。
1 つの入力ファイルにつき、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)
- 1 つの入力ファイルにおける 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) には、i 番目のテストケースにおいて A を並べ替えて等比数列にできる場合は Yes を、そうでない場合は 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
1 つめのテストケースでは、A を並べ替えた (16,8,4,2,1) は、公比 r=\dfrac12 の等比数列になります。
よって、1 行目には Yes と出力してください。
2 つめのテストケースでは、A をどのように並べ替えても条件を満たしません。
よって、2 行目には No と出力してください。
Score : 425 points
Problem Statement
You are given an integer sequence A=(A_1,A_2,\ldots,A_N) of length N. It is guaranteed that for any i\ (1\le i\le N), A_i is not 0.
Determine whether there exists a permutation B=(B_1,B_2,\ldots,B_N) of A such that B forms a geometric sequence.
A sequence S=(S_1,S_2,\ldots,S_N) is a geometric sequence if there exists a real number r such that S_{i+1}=rS_i for all integers 1\le i\lt N.
Solve T test cases per input file.
Constraints
- 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)
- The sum of N over all test cases in a single input file is at most 2\times10^5.
- All input values are integers.
Input
The input is given from standard input in the following format:
T
\mathrm{testcase}_1
\mathrm{testcase}_2
\vdots
\mathrm{testcase}_T
where \mathrm{testcase}_i is the i-th test case (1\le i\le T), and each test case is given in the following format:
N A_1 A_2 \ldots A_N
Output
Output T lines.
The i-th line (1\le i\le T) should contain Yes if A can be rearranged to form a geometric sequence in the i-th test case, and No otherwise.
Sample Input 1
3 5 1 8 2 4 16 5 -16 24 54 81 -36 7 90000 8100 -27000 729 -300000 -2430 1000000
Sample Output 1
Yes No Yes
In the first test case, the rearrangement (16,8,4,2,1) of A forms a geometric sequence with common ratio r=\frac{1}{2}.
Thus, print Yes on the first line.
In the second test case, no rearrangement of A satisfies the condition.
Thus, print No on the second line.