 # SEAARASU - Editorial

### Panel Members

Problem Setter: Sergey Nagin
Problem Tester: Istvan Nagy
Editorialist: Sunny Aggarwal
Russian Translator: Sergey Nagin
Mandarin Translator: Hu Zecong
Vietnamese Translator: VNOI Team
Language Verifier: Rahul Arora

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

Z = \gcd_{{1 \le i \le N }}(A_i)

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:

F_{(a,a)} = a
F_{(a,b)} = F_{(a,b-a)} if(b > a)
F_{(a,b)} = F_{(a-b,b)} if(a > b)

This is actually Greatest Common Divisor (GCD) Function.

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

F_{(a,a,a)} = a
F_{(a,b,c)} = F_{(a,b-a,c)} if(b > a)
F_{(a,b,c)} = F_{(a-b,b,c)} if(a > b)
F_{(a,b,c)} = F_{(a,b,c-a)} if(c > a)
F_{(a,b,c)} = F_{(a-c,b,c)} if(a > c)
F_{(a,b,c)} = F_{(a,b-c,c)} if(b > c)
F_{(a,b,c)} = F_{(a,b,c-b)} if(c > b)

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

Associative Property:

\gcd(a,b,c) = \gcd(a,\gcd(b,c))

Euclid Greatest_common_divisor Algorithm:

\gcd(a,0) = a
\gcd(a,b) = \gcd(b, a \,\mathrm{mod}\, b),

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;
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.

### SIMILAR PROBLEM

Codechef November Long Challenge

Codechef September Cook Off 2013

4 Likes

Where you wrote:

Distributive Property: gcd(a,b,c) = gcd(a,gcd(b,c))

Isn’t that supposed to be Associative Property?

1 Like

This is my first experience of writing editorials for Codechef. Please provide your suggestions to make them better.

@bodmas
Thanks
corrected !!!

Please rejudge the problem with stronger test cases.I stress tested a solution and it gives wrong answer on multiple cases.