The greatest common divisor#571

The greatest common divisor (Editorial)

Written By : MathModel

We can compute the expression by accumulating the GCD , i.e. we can compute the prefix gcd at each time with current index , More formally :

p_{i} = g cd (p_{i - 1}, a_{i})

p_i=\gcd(p_{i-1},a_i)

However , we can observe that we can omit the whole prefix idea with setting $g = a_{1}$ g=a_1 and perform

g \leftarrow g cd (g, a_{i})

g \gets \gcd(g,a_i)

until $i = n$ after that we've $g cd (a_{1}, a_{2}, .., a_{n}) = g$ \gcd(a_1,a_2,..,a_n)=g

Complexity : $O (n \cdot lo g (max (a)))$ \mathcal{O}(n \cdot \log(\max(a))).

since $g cd (x)$ works in $O (lo g x)$ \mathcal{O}(\log x).

from math import *
n=int(input())
a=list(map(int,input().split()))
g=a[0]
for i in a:
   g=gcd(i,g)
print(g)

Python