Little Elephant and Divisors
All submissions for this problem are available.
The Little Elephant from the Zoo of Lviv has an array A that consists of N positive integers. Let A[i] be the i-th number in this array (i = 1, 2, ..., N).
Find the minimal number x > 1 such that x is a divisor of all integers from array A. More formally, this x should satisfy the following relations:
A mod x = 0, A mod x = 0, ..., A[N] mod x = 0,
where mod stands for the modulo operation. For example, 8 mod 3 = 2, 2 mod 2 = 0, 100 mod 5 = 0 and so on. If such number does not exist, output -1.
The first line of the input contains a single integer T, the number of test cases. T test cases follow. The first line of each test case contains a single integer N, the size of the array A for the corresponding test case. The second line contains N space separated integers A, A, ..., A[N].
For each test case output a single line containing the answer for the corresponding test case.
1 ≤ T ≤ 100000
1 ≤ N ≤ 100000
The sum of values of N in each test file does not exceed 100000
1 ≤ A[i] ≤ 100000
Input: 2 3 2 4 8 3 4 7 5 Output: 2 -1
Case 1. Clearly 2 is a divisor of each of the numbers 2, 4 and 8. Since 2 is the least number greater than 1 then it is the answer.
Case 2. Let's perform check for several first values of x.
|x||4 mod x||7 mod x||5 mod x|
As we see each number up to 9 does not divide all of the numbers in the array. Clearly all larger numbers also will fail to do this. So there is no such number x > 1 and the answer is -1.
|Tags||cook28, simple, simple-math, witua|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.6, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, PYP3, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.