2084B.md (1834B)
1 Source: https://codeforces.com/problemset/problem/2084/B 2 3 B. MIN = GCD 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 You are given a positive integer sequence $a$ of length $n$. Determine if it is possible to rearrange $a$ such that there exists an integer $i$ ($1 \le i \lt n$) satisfying $$ \min([a_1,a_2,\ldots,a_i])=\gcd([a_{i+1},a_{i+2},\ldots,a_n]). $$ 22 23 Here $\gcd(c)$ denotes the [greatest common divisor](https://en.wikipedia.org/wiki/Greatest_common_divisor) of $c$, which is the maximum positive integer that divides all integers in $c$. 24 25 Input 26 27 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \le t \le 10^4$). The description of the test cases follows. 28 29 The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$). 30 31 The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^{18}$). 32 33 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 34 35 Output 36 37 For each test case, output "Yes" if it is possible, and "No" otherwise. 38 39 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses. 40 41 Example 42 43 Input 44 45 ``` 46 7 47 48 2 49 50 1 1 51 52 2 53 54 1 2 55 56 3 57 58 2 2 3 59 60 3 61 62 2 3 4 63 64 5 65 66 4 5 6 9 3 67 68 3 69 70 998244359987710471 99824435698771045 1000000007 71 72 6 73 74 1 1 4 5 1 4 75 ``` 76 77 Output 78 79 ``` 80 Yes 81 No 82 Yes 83 No 84 Yes 85 Yes 86 Yes 87 ``` 88 89 Note 90 91 In the first test case, rearrange $a$ to $[1,1]$ and let $i=1$, then $\min([1])=\gcd([1])$. 92 93 In the second test case, it can be shown that it is impossible. 94 95 In the third test case, rearrange $a$ to $[3,2,2]$ and let $i=2$, then $\min([3,2])=\gcd([2])$. 96 97 In the fifth test case, rearrange $a$ to $[3,4,5,6,9]$ and let $i=3$, then $\min([3,4,5])=\gcd([6,9])$.