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.