codeforces-scrape

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

1933D.md (1990B)


      1 Source: https://codeforces.com/problemset/problem/1933/D
      2 
      3 D. Turtle Tenacity: Continual Mods
      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 Given an array $a_1, a_2, \ldots, a_n$, determine whether it is possible to rearrange its elements into $b_1, b_2, \ldots, b_n$, such that $b_1 \bmod b_2 \bmod \ldots \bmod b_n \neq 0$.
     22 
     23 Here $x \bmod y$ denotes the remainder from dividing $x$ by $y$. Also, the modulo operations are calculated from left to right. That is, $x \bmod y \bmod z = (x \bmod y) \bmod z$. For example, $2024 \bmod 1000 \bmod 8 = (2024 \bmod 1000) \bmod 8 = 24 \bmod 8 = 0$.
     24 
     25 Input
     26 
     27 The first line of the input contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases.
     28 
     29 The first line of each test case contains a single integer $n$ ($2 \le n \le 10^5$).
     30 
     31 The second line of each test case contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 10^9$).
     32 
     33 The sum of $n$ over all test cases does not exceed $2 \cdot 10^5$.
     34 
     35 Output
     36 
     37 For each test case, output "YES" if it is possible, "NO" otherwise.
     38 
     39 You can output the answer in any case (upper or lower). For example, the strings "yEs", "yes", "Yes", and "YES" will be recognized as positive responses.
     40 
     41 Example
     42 
     43 Input
     44 
     45 ```
     46 8
     47 
     48 6
     49 
     50 1 2 3 4 5 6
     51 
     52 5
     53 
     54 3 3 3 3 3
     55 
     56 3
     57 
     58 2 2 3
     59 
     60 5
     61 
     62 1 1 2 3 7
     63 
     64 3
     65 
     66 1 2 2
     67 
     68 3
     69 
     70 1 1 2
     71 
     72 6
     73 
     74 5 2 10 10 10 2
     75 
     76 4
     77 
     78 3 6 9 3
     79 ```
     80 
     81 Output
     82 
     83 ```
     84 YES
     85 NO
     86 YES
     87 NO
     88 YES
     89 NO
     90 YES
     91 NO
     92 ```
     93 
     94 Note
     95 
     96 In the first test case, rearranging the array into $b = [1, 2, 3, 4, 5, 6]$ (doing nothing) would result in $1 \bmod 2 \bmod 3 \bmod 4 \bmod 5 \bmod 6 = 1$. Hence it is possible to achieve the goal.
     97 
     98 In the second test case, the array $b$ must be equal to $[3, 3, 3, 3, 3]$, which would result in $3 \bmod 3 \bmod 3 \bmod 3 \bmod 3 = 0$. Hence it is impossible to achieve the goal.
     99 
    100 In the third test case, rearranging the array into $b = [3, 2, 2]$ would result in $3 \bmod 2 \bmod 2 = 1$. Hence it is possible to achieve the goal.