Read problems statements in Mandarin chinese, Russian and Vietnamese as well. 

Chef has a sequence $A$ consisting of $N$ positive integers. 

He is playing a game with this sequence. The goal of the game is to maximize the greatest common divisor of all elements of the sequence. Chef may perform the following operation an arbitrary number of times (including zero):
Choose a positive integer $d$ and a valid index $i$ such that $A_{i}$ is divisible by $d^{2}$.
Divide $A_{i}$ by $d^{2}$.
Choose a valid index $j$ (not necessarily different from $i$) and multiply $A_{j}$ by $d$.

Help Chef and find the maximum GCD of all integers in the sequence he could obtain if he plays optimally!

------  Input ------
The first line of the input contains a single integer $T$ denoting the number of test cases. The description of $T$ test cases follows.
The first line of each test case contains a single integer $N$.
The second line contains $N$ space-separated integers $A_{1}, A_{2}, \dots, A_{N}$.
 
------  Output ------
For each test case, print a single line containing one integer — the maximum possible value of the greatest common divisor of all elements of the sequence.

------  Constraints  ------
$1 ≤ T ≤ 5$
$1 ≤ N ≤ 10^{5}$
$1 ≤ A_{i} ≤ 10^{6}$ for each valid $i$

----- Sample Input 1 ------ 
2
2
1 25
5
27 3 15 1024 15
----- Sample Output 1 ------ 
1
6

Source: codechef | Difficulty: VERY_HARD
Tags: Number theory

Sorting

Mathematics

Complete search


Solutions:
def findmin(m, arr):
	st = -1
	en = n - 1
	while en - st > 1:
		md = (st + en) // 2
		if arr[md] < m:
			st = md
		else:
			en = md
	return en
sv = [True] * 101
bpr = [2]
for ap in range(3, 101, 2):
	if sv[ap]:
		bpr.append(ap)
		for ml in range(ap * ap, 101, ap):
			sv[ml] = False

def facd(a):
	rdic = dict()
	for ap in bpr:
		if 0 == a % ap:
			a //= ap
			rdic[ap] = 1
			while 0 == a % ap:
				a //= ap
				rdic[ap] += 1
			if a < ap * ap:
				break
	if a > 1:
		rdic[a] = 1
	return rdic
for _ in range(int(input())):
	n = int(input())
	z = input().split()
	a = list(map(int, z[:n]))
	g = a[0]
	for ai in a:
		ai %= g
		while ai > 0:
			(g, ai) = (ai, g % ai)
		if g == 1:
			break
	if g > 1:
		a = [ai // g for ai in a]
	faclib = [facd(ai) for ai in a]
	for ap in bpr:
		mult = []
		for adic in faclib:
			m = 0
			if ap in adic:
				m = adic[ap]
			mult.append(m)
		if sum(mult) > n:
			mult.sort()
			thr = 1
			nbt = 0
			while True:
				nbt += findmin(thr, mult)
				nsup = findmin(thr + 2, mult)
				surp = (sum(mult[nsup:n]) - thr * (n - nsup)) // 2
				if surp < nbt:
					break
				g *= ap
				thr += 1
	print(g)


sv = [True] * 101
bpr = [2]
for ap in range(3, 101, 2):
	if sv[ap]:
		bpr.append(ap)
		for ml in range(ap * ap, 101, ap):
			sv[ml] = False
for _ in range(int(input())):
	n = int(input())
	z = input().split()
	a = list(map(int, z[:n]))
	g = a[0]
	for ai in a:
		ai %= g
		while ai > 0:
			(g, ai) = (ai, g % ai)
		if g == 1:
			break
	if g > 1:
		a = [ai // g for ai in a]
	for ap in bpr:
		mult = []
		for ai in a:
			m = 0
			while 0 == ai % ap:
				ai //= ap
				m += 1
			mult.append(m)
		while sum(mult) > n:
			mult.sort()
			st = 0
			en = n - 1
			while mult[st] == 0 and mult[en] > 2:
				mult[st] += 1
				st += 1
				mult[en] -= 2
				en -= 1
				if mult[en] <= 2:
					en = n - 1
			if mult[st] == 0:
				break
			g *= ap
			mult = [m - 1 for m in mult]
	print(g)