1081. 最大公因数排序

有两个数列,数列 A={a[1],a[2],...,a[n]} 和数列 B={b[1],b[2],...,b[n]}

对于数列 B 中的每一项 b[i] 都有 b[i]=2^{a[i]},你可以对 B 进行以下操作。

minB 里面最小的数,gcd(x,y)x,y 的最大公因数。

对于 b[i],b[j] \ (i≠j) 如果有 gcd(b[i],b[j])=min 那么你可以交换 b[i],b[j] 的位置。

如果能在有限次操作内把 B 序列调整为有序数列,如果可以则输出 Yes,否则输出 No

输入

第一行输入一个整数 T \ (1 \leq T \leq 20),表示有 T 组数据。

每组数据的第一行输入 n \ (1 \leq n \leq 10^5),表示数列大小。

每组数据的第二行输入 n 个数,第 i 个数表示数列 A 的第 i 个数 a[i] \ (0 \leq a[i] \leq 10^9)

输出

如果能在有限次操作内把 B 序列调整为有序数列,如果可以则输出 Yes,否则输出 No

样例

标准输入 复制文本
2
4
3 2 1 4
3
0 1 2
标准输出 复制文本
Yes
Yes

来源

广东工业大学 2020 年 ACM 第一次月赛

登录以提交代码。
单点时限 1 秒
内存限制 128 MB
提交 124
通过 48