「MYOI-R3」消消乐
题目背景
**upd 2024/5/12 18:14:增加了两组 Hack 数据,位于 Subtask 1,分值为 $0$ 分。**
**upd 2024/5/12 21:27:增加了一组 Hack 数据,位于 Subtask 1,分值为 $0$ 分。**
题目描述
给定一个长度为 $n$ 的数列 $a$。
定义一次操作为选择三个整数 $x,y,z\in[1,n]$,满足 $\gcd(a_x,a_y)=a_z$ 且 $x,y,z$ 两两不同,接着消除 $a_z$(即之后的操作中不能再选择 $a_z$ 了)。
问经过若干次操作后可否消除数列 $a_1\sim a_n$ 中的 $n-2$ 个数?
输入输出格式
输入格式
第一行一个正整数 $T$,表示数据组数。
对于每组数据,
第一行一个正整数 $n$。
第二行 $n$ 个正整数 $a_i$。
输出格式
对于每组数据,一行一个字符串 `Yes` 或 `No`。
输入输出样例
输入样例 #1
2
3
1 2 3
3
1 2 4
输出样例 #1
Yes
No
说明
### 样例解释:
- 对于第一组数据,可以通过 $(2,3)$ 消除 $1$。
- 对于第二组数据,可以证明无解。
### 数据范围:
本题共有 $20$ 个测试点,每个测试点的分值均为 $5$ 分。
对于 $100\%$ 的数据,$1\le T\le 10^5$,$2\leq n \leq 10^6$,$2 \le \sum n\le 10^6$,$1\le a_i\le 10^9$。