2126E.md (2219B)
1 Source: https://codeforces.com/problemset/problem/2126/E 2 3 E. G-C-D, Unlucky! 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 Two arrays $p$ and $s$ of length $n$ are given, where $p$ is the prefix GCD$^{\text{∗}}$ of some array $a$, and $s$ is the suffix GCD of the same array $a$. In other words, if the array $a$ existed, then for each $1 \le i \le n$, the following equalities would hold both: 22 23 * $p_i = \gcd(a_1, a_2, \dots, a_i)$ 24 * $s_i = \gcd(a_i, a_{i+1}, \dots, a_n)$. 25 26 Determine whether there exists such an array $a$ for which the given arrays $p$ and $s$ can be obtained. 27 28 $^{\text{∗}}$$\gcd(x, y)$ denotes the [greatest common divisor (GCD)](https://en.wikipedia.org/wiki/Greatest_common_divisor) of integers $x$ and $y$. 29 30 Input 31 32 The first line contains an integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 33 34 Each test case consists of three lines: 35 36 The first line of each test case contains a single integer $n$ ($1 \leq n \leq 10^5$) — the length of the array. 37 38 The second line of each test case contains $n$ integers $p_1, p_2, \dots, p_n$ ($1 \leq p_i \le 10^9$) — the elements of the array. 39 40 The third line of each test case contains $n$ integers $s_1, s_2, \dots, s_n$ ($1 \leq s_i \le 10^9$) — the elements of the array. 41 42 It is guaranteed that the sum of all $n$ across all test cases does not exceed $10^5$. 43 44 Output 45 46 For each test case, output "Yes" (without quotes) if there exists an array $a$ for which the given arrays $p$ and $s$ can be obtained, and "No" (without quotes) otherwise. 47 48 You may output each letter in any case (lowercase or uppercase). For example, the strings "yEs", "yes", "Yes", and "YES" will be accepted as a positive answer. 49 50 Example 51 52 Input 53 54 ``` 55 5 56 57 6 58 59 72 24 3 3 3 3 60 61 3 3 3 6 12 144 62 63 3 64 65 1 2 3 66 67 4 5 6 68 69 5 70 71 125 125 125 25 25 72 73 25 25 25 25 75 74 75 4 76 77 123 421 282 251 78 79 125 1981 239 223 80 81 3 82 83 124 521 125 84 85 125 121 121 86 ``` 87 88 Output 89 90 ``` 91 YES 92 NO 93 YES 94 NO 95 NO 96 ``` 97 98 Note 99 100 For the first test case, a possible array is: [$72,\ 24,\ 3,\ 6,\ 12,\ 144$]. 101 102 For the second test case, it can be shown that such arrays do not exist. 103 104 For the third test case, there exists an array: [$125,\ 125,\ 125,\ 25,\ 75$].