1980D.md (2469B)
1 Source: https://codeforces.com/problemset/problem/1980/D 2 3 D. GCD-sequence 4 5 time limit per test 6 7 2 seconds 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 GCD (Greatest Common Divisor) of two integers $x$ and $y$ is the maximum integer $z$ by which both $x$ and $y$ are divisible. For example, $GCD(36, 48) = 12$, $GCD(5, 10) = 5$, and $GCD(7,11) = 1$. 22 23 Kristina has an array $a$ consisting of exactly $n$ positive integers. She wants to count the GCD of each neighbouring pair of numbers to get a new array $b$, called GCD-sequence. 24 25 So, the elements of the GCD-sequence $b$ will be calculated using the formula $b_i = GCD(a_i, a_{i + 1})$ for $1 \le i \le n - 1$. 26 27 Determine whether it is possible to remove exactly one number from the array $a$ so that the GCD sequence $b$ is non-decreasing (i.e., $b_i \le b_{i+1}$ is always true). 28 29 For example, let Khristina had an array $a$ = [$20, 6, 12, 3, 48, 36$]. If she removes $a_4 = 3$ from it and counts the GCD-sequence of $b$, she gets: 30 31 * $b_1 = GCD(20, 6) = 2$ 32 * $b_2 = GCD(6, 12) = 6$ 33 * $b_3 = GCD(12, 48) = 12$ 34 * $b_4 = GCD(48, 36) = 12$ 35 36 The resulting GCD sequence $b$ = [$2,6,12,12$] is non-decreasing because $b_1 \le b_2 \le b_3 \le b_4$. 37 38 Input 39 40 The first line of input data contains a single number $t$ ($1 \le t \le 10^4$) — he number of test cases in the test. 41 42 This is followed by the descriptions of the test cases. 43 44 The first line of each test case contains a single integer $n$ ($3 \le n \le 2 \cdot 10^5$) — the number of elements in the array $a$. 45 46 The second line of each test case contains exactly $n$ integers $a_i$ ($1 \le a_i \le 10^9$) — the elements of array $a$. 47 48 It is guaranteed that the sum of $n$ over all test case does not exceed $2 \cdot 10^5$. 49 50 Output 51 52 For each test case, output a single line: 53 54 * "YES" if you can remove exactly one number from the array $a$ so that the GCD-sequence of $b$ is non-decreasing; 55 * "NO" otherwise. 56 57 You can output the answer in any case (for example, the strings "yEs", "yes", "Yes", and "YES" will all be recognized as a positive answer). 58 59 Example 60 61 Input 62 63 ``` 64 12 65 66 6 67 68 20 6 12 3 48 36 69 70 4 71 72 12 6 3 4 73 74 3 75 76 10 12 3 77 78 5 79 80 32 16 8 4 2 81 82 5 83 84 100 50 2 10 20 85 86 4 87 88 2 4 8 1 89 90 10 91 92 7 4 6 2 4 5 1 4 2 8 93 94 7 95 96 5 9 6 8 5 9 2 97 98 6 99 100 11 14 8 12 9 3 101 102 9 103 104 5 7 3 10 6 3 12 6 3 105 106 3 107 108 4 2 4 109 110 8 111 112 1 6 11 12 6 12 3 6 113 ``` 114 115 Output 116 117 ``` 118 YES 119 NO 120 YES 121 NO 122 YES 123 YES 124 NO 125 YES 126 YES 127 YES 128 YES 129 YES 130 ``` 131 132 Note 133 134 The first test case is explained in the problem statement.