← 返回题目列表

Codeforces · 2084/B

B. 最小值 = GCD

中文机器翻译题面 查看原题

给定一个长度为 $$$n$$$ 的正整数序列 $$$a$$$。确定是否可以重新排列$$$a$$$,使得存在满足$$$$$$ \min([a_1,a_2,\ldots,a_i])=\gcd([a_{i+1},a_{i+2},\ldots,a_n])的整数$$$i$$$ ($$$1 \le i \lt n$$$)。 $$$$$$

这里$$$\gcd(c)$$$表示$$$c$$$的最大公约数,它是整除$$$c$$$中所有整数的最大正整数。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$2 \le n \le 10^5$$$)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \le a_i \le 10^{18}$$$)。

保证所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,输出“是“如果可能的话,并且”No”否则。

您可以在任何情况下输出答案(大写或小写)。例如,字符串“是", "是的", "是“,和”是”将被视为积极响应。

示例

输入
复制

7
2
1 1
2
1 2
3
2 2 3
3
2 3 4
5
4 5 6 9 3
3
998244359987710471 99824435698771045 1000000007
6
1 1 4 5 1 4

输出
复制

Yes
No
Yes
No
Yes
Yes
Yes

注意

在第一个测试用例中,将 $$$a$$$ 重新排列为 $$$[1,1]$$$ 并让 $$$i=1$$$,然后 $$$\min([1])=\gcd([1])$$$。

在第二个测试用例中,可以证明这是不可能的。

在第三个测试用例中,将 $$$a$$$ 重新排列为 $$$[3,2,2]$$$ 并让 $$$i=2$$$,然后 $$$\min([3,2])=\gcd([2])$$$。

在第五个测试用例中,将 $$$a$$$ 重新排列为 $$$[3,4,5,6,9]$$$ 并让 $$$i=3$$$,然后 $$$\min([3,4,5])=\gcd([6,9])$$$。