G - Unique Factorization ?
Flavor
5
s
1024
MB
700
点
問題文
$N$ 個の $2$ 以上の整数 $A_1, A_2, \ldots, A_N$ が与えられます。次の条件を満たすかを判定してください。
- $2$ つの長さ $N$ の非負整数列 $s = (s_1, \ldots, s_N), t = (t_1, \ldots, t_N)$ が存在し、以下を満たす。
- $s \neq t$
- $A_1^{s_1} \cdots A_N^{s_N} = A_1^{t_1} \cdots A_N^{t_N}$
$T$ 個のテストケースについて答えてください。
制約
- $1 \le T \le 5$
- $1\leq N \leq 2 \times 10^5$
- $2 \le A_i \le 5 \times 10^6$
- $i \neq j$ ならば $A_i \neq A_j$
- 入力は全ては整数
入力
入力は以下の形式で標準入力から与えられます。ここで $\mathrm{test}_i$ は $i$ 番目のテストケースを意味します。
$T$
$\mathrm{test}_1$
$\mathrm{test}_2$
$\vdots$
$\mathrm{test}_T$
各テストケースは以下の形式で与えられます。
$N$
$A_1 \space A_2 \space \ldots \space A_N$
出力
$T$ 行出力してください。
$i$ 行目には、$i$ 番目のテストケースが条件を満たす場合は Yes を、満たさない場合は No を出力してください。
入力例 1
4
3
2 3 6
2
2 6
10
22 57 145 161 221 46 377 21 95 187
10
44 57 145 161 221 46 377 21 95 187
出力例 1
Yes
No
Yes
No
この入力には $4$ 個のテストケースが含まれます。
$1$ 個目のテストケースは $A_1 = 2, A_2 = 3, A_3 = 6$ です。
このとき $A_1^1 A_2^1 A_3^0 = A_1^0 A_2^0 A_3^1$ となるため、問題文の条件を満たします。
$2$ 個目のテストケースは $A_1 = 2, A_2 = 6$ です。
このとき非負整数 $s_1, s_2, t_1, t_2$ に対して $A_1^{s_1} A_2^{s_2} = A_1^{t_1} A_2^{t_2}$ を満たすと仮定すると、$s_1 = t_1, s_2 = t_2$ となることが示せます。
ゆえに問題文の条件を満たしません。