1081. 最大公因数排序

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

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

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

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

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

输入

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

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

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

输出

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

样例

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

来源

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

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