1975B.md (1918B)
1 Source: https://codeforces.com/problemset/problem/1975/B 2 3 B. 378QAQ and Mocha's Array 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 Mocha likes arrays, so before her departure, 378QAQ gave her an array $a$ consisting of $n$ positive integers as a gift. 22 23 Mocha thinks that $a$ is beautiful if there exist two numbers $i$ and $j$ ($1\leq i,j\leq n$, $i\neq j$) such that for all $k$ ($1 \leq k \leq n$), $a_k$ is divisible$^\dagger$ by either $a_i$ or $a_j$. 24 25 Determine whether $a$ is beautiful. 26 27 $^\dagger$ $x$ is divisible by $y$ if there exists an integer $z$ such that $x = y \cdot z$. 28 29 Input 30 31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\leq t\leq 500$). The description of the test cases follows. 32 33 The first line of each test case contains a single integer $n$ ($3\leq n\leq 10^5$) — the length of the array $a$. 34 35 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq a_i \leq 10^9$) — the elements of the array $a$. 36 37 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 38 39 Output 40 41 For each test case, output "Yes" if array $a$ is beautiful, and output "No" otherwise. 42 43 You can output "Yes" and "No" in any case (for example, strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive response). 44 45 Example 46 47 Input 48 49 ``` 50 4 51 52 3 53 54 7 3 8 55 56 5 57 58 7 1 9 3 5 59 60 5 61 62 4 12 2 6 3 63 64 5 65 66 7 49 9 3 1000000000 67 ``` 68 69 Output 70 71 ``` 72 No 73 Yes 74 Yes 75 No 76 ``` 77 78 Note 79 80 In the first test case, any two numbers in the array are coprime, so the answer is "No". 81 82 In the second test case, we can pick $i=2$ and $j=1$. Since every number in the array is divisible by $a_i = 1$, the answer is "Yes". 83 84 In the third test case, we can pick $i=3$ and $j=5$. $2$ and $4$ is divisible by $a_i = 2$ while $3$, $6$ and $12$ is divisible by $a_j = 3$, so the answer is "Yes".