codeforces-scrape

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

1975B.md (1918B)


      1 Source: https://codeforces.com/problemset/problem/1975/B
      2 
      3 B. 378QAQ and Mocha's Array
      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 Mocha likes arrays, so before her departure, 378QAQ gave her an array $a$ consisting of $n$ positive integers as a gift.
     22 
     23 Mocha thinks that $a$ is beautiful if there exist two numbers $i$ and $j$ ($1\leq i,j\leq n$, $i\neq j$) such that for all $k$ ($1 \leq k \leq n$), $a_k$ is divisible$^\dagger$ by either $a_i$ or $a_j$.
     24 
     25 Determine whether $a$ is beautiful.
     26 
     27 $^\dagger$ $x$ is divisible by $y$ if there exists an integer $z$ such that $x = y \cdot z$.
     28 
     29 Input
     30 
     31 Each test contains multiple test cases. The first line contains the number of test cases $t$ ($1\leq t\leq 500$). The description of the test cases follows.
     32 
     33 The first line of each test case contains a single integer $n$ ($3\leq n\leq 10^5$) — the length of the array $a$.
     34 
     35 The second line of each test case contains $n$ integers $a_1,a_2,\ldots,a_n$ ($1\leq a_i \leq 10^9$) — the elements of the array $a$.
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     38 
     39 Output
     40 
     41 For each test case, output "Yes" if array $a$ is beautiful, and output "No" otherwise.
     42 
     43 You can output "Yes" and "No" in any case (for example, strings "yEs", "yes", "Yes" and "YES" will be recognized as a positive response).
     44 
     45 Example
     46 
     47 Input
     48 
     49 ```
     50 4
     51 
     52 3
     53 
     54 7 3 8
     55 
     56 5
     57 
     58 7 1 9 3 5
     59 
     60 5
     61 
     62 4 12 2 6 3
     63 
     64 5
     65 
     66 7 49 9 3 1000000000
     67 ```
     68 
     69 Output
     70 
     71 ```
     72 No
     73 Yes
     74 Yes
     75 No
     76 ```
     77 
     78 Note
     79 
     80 In the first test case, any two numbers in the array are coprime, so the answer is "No".
     81 
     82 In the second test case, we can pick $i=2$ and $j=1$. Since every number in the array is divisible by $a_i = 1$, the answer is "Yes".
     83 
     84 In the third test case, we can pick $i=3$ and $j=5$. $2$ and $4$ is divisible by $a_i = 2$ while $3$, $6$ and $12$ is divisible by $a_j = 3$, so the answer is "Yes".