1736B.md (1517B)
1 Source: https://codeforces.com/problemset/problem/1736/B 2 3 B. Playing with 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 an integer array $a$ of length $n$. 22 23 Does there exist an array $b$ consisting of $n+1$ positive integers such that $a_i=\gcd (b_i,b_{i+1})$ for all $i$ ($1 \leq i \leq n$)? 24 25 Note that $\gcd(x, y)$ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $x$ and $y$. 26 27 Input 28 29 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1 \leq t \leq 10^5$). Description of the test cases follows. 30 31 The first line of each test case contains an integer $n$ ($1 \leq n \leq 10^5$) — the length of the array $a$. 32 33 The second line of each test case contains $n$ space-separated integers $a_1,a_2,\ldots,a_n$ representing the array $a$ ($1 \leq a_i \leq 10^4$). 34 35 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$. 36 37 Output 38 39 For each test case, output "YES" if such $b$ exists, otherwise output "NO". You can print each letter in any case (upper or lower). 40 41 Example 42 43 Input 44 45 ``` 46 4 47 48 1 49 50 343 51 52 2 53 54 4 2 55 56 3 57 58 4 2 4 59 60 4 61 62 1 1 1 1 63 ``` 64 65 Output 66 67 ``` 68 YES 69 YES 70 NO 71 YES 72 ``` 73 74 Note 75 76 In the first test case, we can take $b=[343,343]$. 77 78 In the second test case, one possibility for $b$ is $b=[12,8,6]$. 79 80 In the third test case, it can be proved that there does not exist any array $b$ that fulfills all the conditions.