Square in numbers
All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Leha is a bright mathematician. Today he is investigating whether an integer is divisible by some square number or not.
He has a positive integer X represented as a product of N integers a1, a2, .... aN. He has somehow figured out that there exists some integer P such that the number X is divisible by P2, but he is not able to find such P himself. Can you find it for him? If there are more than one possible values of P possible, you can print any one of them.
The first line of the input contains an integer T denoting the number of test cases. T test cases follow.
The first line of each test case contains one integer N denoting the number of intgers in presentation of X.
The second line contains N space-separated integers a1, a2, .... aN.
For each test case, output a single integer P deoting the answer for this test case. Note that P must be in range from 2 to 1018 inclusive. It's guaranteed that at least one answer exists. If there are more than one possible answers, print any.
- 1 ≤ T ≤ 5
- 1 ≤ N ≤ 100
- 1 ≤ ai ≤ 1018
- Subtask 1[19 points]: 1 ≤ a1*a2*...*aN ≤ 106
- Subtask 2[22 points]: 1 ≤ a1*a2*...*aN ≤ 1012
- Subtask 3[23 points]: 1 ≤ ai ≤ 1012
- Subtask 4[36 points]: no additional constraints
Input: 1 3 21 11 6 Output: 3
Example case 1. X = 21 * 11 * 6 = 1386. It's divisible by 9 which is a square number, as 9 = 32. So P = 3.
|Tags||ltime37, medium, number-theory, pavel1996|
|Time Limit:||2 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, 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, SCM chicken, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.