# PROBLEM LINK:

Practice

Contest: Division 1

Contest: Division 2

Contest: Division 3

Contest: Division 4

* Author:* Ram Gopal Pandey

*Souradeep Paul*

**Preparer:***Takuki Kurokawa, Utkarsh Gupta*

**Testers:***Nishank Suresh*

**Editorialist:**# DIFFICULTY:

1315

# PREREQUISITES:

None

# PROBLEM:

You have an array of length N. In one move, you can replace 2 elements by their gcd. What is the minimum possible sum of the final array?

# EXPLANATION

Let G = \gcd(A_1, A_2, \ldots, A_N). The answer is simply N \cdot G.

Clearly, it is not possible to make any element less than G because G divides every element of A. Conversely, it is possible to make every element equal to G - to make the i-th element equal to G, perform the operations on (1, i), (2, i), (3, i), \ldots, (N, i).

All that remains is to compute G. This is easy - using the fact that \gcd(a, b, c) = \gcd(a, \gcd(b, c)), we can simply initialize G to A_1, and then run a loop of i from 2 to N, each time doing G \gets \gcd(G, A_i).

# TIME COMPLEXITY:

\mathcal{O}(N + \log M) per test case, where M is the maximum element of the array.

# CODE:

## Editorialist's code (Python)

```
import math
for _ in range(int(input())):
n = int(input())
a = list(map(int, input().split()))
print(n * math.gcd(*a))
```