codeforces-scrape

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

1771C.md (1426B)


      1 Source: https://codeforces.com/problemset/problem/1771/C
      2 
      3 C. Hossam and Trainees
      4 
      5 time limit per test
      6 
      7 3 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 Hossam has $n$ trainees. He assigned a number $a_i$ for the $i$-th trainee.
     22 
     23 A pair of the $i$-th and $j$-th ($i \neq j$) trainees is called successful if there is an integer $x$ ($x \geq 2$), such that $x$ divides $a_i$, and $x$ divides $a_j$.
     24 
     25 Hossam wants to know if there is a successful pair of trainees.
     26 
     27 Hossam is very tired now, so he asks you for your help!
     28 
     29 Input
     30 
     31 The input consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^5$), the number of test cases. A description of the test cases follows.
     32 
     33 The first line of each test case contains an integer number $n$ ($2 \le n \le 10^5$).
     34 
     35 The second line of each test case contains $n$ integers, the number of each trainee $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^9$).
     36 
     37 It is guaranteed that the sum of $n$ over all test cases does not exceed $10^5$.
     38 
     39 Output
     40 
     41 Print the answer — "YES" (without quotes) if there is a successful pair of trainees and "NO" otherwise. You can print each letter in any case.
     42 
     43 Example
     44 
     45 Input
     46 
     47 ```
     48 2
     49 
     50 3
     51 
     52 32 48 7
     53 
     54 3
     55 
     56 14 5 9
     57 ```
     58 
     59 Output
     60 
     61 ```
     62 YES
     63 NO
     64 ```
     65 
     66 Note
     67 
     68 In the first example, the first trainee and the second trainee make up a successful pair:
     69 
     70 $a_1 = 32, a_2 = 48$, you can choose $x = 4$.