codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$].