*“You can make a lot by playing such games.”*

Every player has to play a game of Ddakji with the recruiter in order to enter the squid game. Gi-Hun has played many rounds but was unable to win even once. The recruiter thus decided to give him a puzzle instead.

Gi-Hun is given an array A of N elements.
He can perform the following operation on array A any number of times:
Select any two indexes 1 ≤ i, j ≤ N such that i \neq j and replace A_{i} with A_{i} - A_{j}.

His task is to find the minimum possible value of |A_{1}| + |A_{2}| + \ldots + |A_{N}| attainable by performing these operations several (possibly, 0) times.

------ Input Format ------ 

- The first line of 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 N, the number of elements in the array.
- The second line of each test case contains N space-separated integers — A_{1}, A_{2}, \ldots, A_{N}.

------ Output Format ------ 

For each testcase, print on a new line one integer — minimum possible value of |A_{1}| + |A_{2}| + \ldots + |A_{N}|.

------ Constraints ------ 

$1 ≤ T ≤ 10^{5}$
$2 ≤ N ≤ 10^{5}$
$-10^{9} ≤ A_{i} ≤ 10^{9}$
- Sum of $N$ across all test cases doesn't exceed $10^{6}$

----- Sample Input 1 ------ 
5
2
4 1
5
0 0 0 0 0
5
10 10 10 10 10
4
0 2 -2 6
10
10 9 8 7 6 -5 -4 -3 -2 -1
----- Sample Output 1 ------ 
1
0
10
4
2
----- explanation 1 ------ 
Test Case 1: Perform the operation with $i = 1$ and $j = 2$ four times. The array is now $[0, 1]$, and its value is $|0| + |1| = 1$.

Test Case 2: No operations need to be performed.

Test Case 4: Perform the following operations:
- Choose $i = 4, j = 2$ and set $A_{4} = 6 - 2 = 4$. The array is now $[0, 2, -2, 4]$.
- Choose $i = 4, j = 2$ and set $A_{4} = 4 - 2 = 2$. The array is now $[0, 2, -2, 2]$.
- Choose $i = 2, j = 4$ and set $A_{2} = 2 - 2 = 0$. The array is now $[0, 0, -2, 2]$.

The value of the array is now $|0| + |0| + |-2| + |2| = 4$, and it can be proved that this is the minimum possible value.

Difficulty: VERY_HARD
Tags: Number theory

Mathematics

Ad-hoc

Starter code:

Solutions:
import math

def getGCD(arr):
	lenArr = len(arr)
	if lenArr == 0:
		return 0
	if lenArr == 1:
		return arr[0]
	ans = arr[0]
	for i in arr[1:lenArr]:
		ans = math.gcd(ans, i)
		if ans == 1:
			return ans
	return ans
import math
t = int(input())
for _ in range(t):
	n = int(input())
	a = list(map(int, input().split()))
	pos = []
	neg = []
	for i in a:
		if i > 0:
			pos.append(i)
		elif i < 0:
			neg.append(-i)
	gp = getGCD(pos)
	gn = getGCD(neg)
	if n > 2 and len(pos) * len(neg) > 0:
		ans = 2 * math.gcd(gp, gn)
	else:
		ans = gp + gn
	print(ans)


from math import gcd
for _ in range(int(input())):
	n = int(input())
	x = list(map(int, input().split()))
	pos = []
	neg = []
	for i in range(n):
		if x[i] > 0:
			pos += [x[i]]
		elif x[i] < 0:
			neg += [-x[i]]
	if len(pos) == 0:
		g1 = 0
	else:
		g1 = pos[0]
		for i in range(1, len(pos)):
			g1 = gcd(g1, pos[i])
			if g1 == 1:
				break
	if len(neg) == 0:
		g2 = 0
	else:
		g2 = neg[0]
		for i in range(1, len(neg)):
			g2 = gcd(g2, neg[i])
			if g2 == 1:
				break
	if g1 == 0 or g2 == 0:
		print(g1 + g2)
	elif n == 2 and g1 > 0 and (g2 > 0):
		print(g1 + g2)
	else:
		print(2 * gcd(g1, g2))