### PROBLEM LINK

### Panel Members

**Problem Setter:** Sergey Nagin

**Problem Tester:** Istvan Nagy

**Editorialist:** Sunny Aggarwal

**Contest Admin:** Praveen Dhinwa

**Russian Translator:** Sergey Nagin

**Mandarin Translator:** Hu Zecong

**Vietnamese Translator:** VNOI Team

**Language Verifier:** Rahul Arora

### DIFFICULTY:

Easy

### PREREQUISITES:

Number Theory, Greatest Common Divisor \left(\gcd\right), Maths

### PROBLEM:

Given an array A consisting of N positive integers. In an operation, you will choose two indices i and j, such that A_i \gt A_j and then subtract number A_j from number A_i. Find the minimum possible sum of the array after applying above operation any number of times.

### QUICK EXPLANATION

It is easy to notice that after applying all the operations, all the values in the given array will be equal otherwise we can still choose a pair of indices i and j such that A_i \gt A_j and can reduce the sum further. Value of each element after applying all the operation will be equal to Z.

where

Therefore, minimum possible sum will be equal to N * Z.

### EXPLANATION

Lets solve this problem for some smaller cases.

**Example 1:** N = 2 where A_0 = 5 and A_1 = 15.

After 1^{st} operation, A_0 = 5, A_1 = 10.

After 2^{nd} operation, A_0 = 5, A_1 = 5.

**NOTE** A_0 = A_1 = 5 and we cannot make any further reductions.

**Example 2:** N = 2 where A_0 = 7 and A_1 = 3.

After 1^{st} operation, A_0 = 4, A_1 = 3.

After 2^{nd} operation, A_0 = 1, A_1 = 3.

After 3^{rd} operation, A_0 = 1, A_1 = 2.

After 4^{th} operation, A_0 = 1, A_1 = 1.

**NOTE** A_0 = A_1 = 1 and we cannot make any further reductions.

Lets generalise the case for 2 elements say for a and b. Let us consider that the function F_{(a, b)} denotes the minimum equal value that we can achieved by applying given operation

on a and b any number of times.

**Function F can be written as:**

This is actually Greatest Common Divisor (GCD) Function.

**For 3 elements a, b, and c. Function F can be written as:**

which is equivalent to the \gcd(a,b,c).

**Associative Property:**

**Euclid Greatest_common_divisor Algorithm:**

**Euclidean GCD C ++ code:**

```
// Euclidean GCD Algorithm
int gcd(int a, int b) {
if(b == 0) {
return a;
}
return gcd(b, a%b);
}
```

or inbuilt **__gcd()** function available in C ++.

**Solution code:**

```
int A[N+1];
long long int Z = A[1];
for(int i=2; i<=N; i++) {
Z = __gcd(ans, A[i]);
}
Z = Z * N; // final answer
// be careful for the overflow use long long int
```

### COMPLEXITY

O(N\log(\max(A_i)))

### AUTHORâ€™S AND TESTERâ€™S SOLUTIONS:

The authorâ€™s solution can be found here.

The testerâ€™s solution can be found here.

The editorialistâ€™s solution can be found here.