PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: Ram Gopal Pandey
Preparer: Souradeep Paul
Testers: Takuki Kurokawa, Utkarsh Gupta
Editorialist: Nishank Suresh
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))