Trivial? Solve It!#14

Trivial? Solve It! (Editorial)

We will use the property of the greatest common divisor  — \gcd(a,b)=\gcd(a,b-a).

We will generalize it to the set a_1,\dots,a_n: \gcd(a_1,a_2,\dots,a_n)=\gcd(a_1,a_2-a_1,\dots,a_n-a_1).

After the operation to the entire array, we get

\gcd(a_1+x,a_2+x,\dots,a_n+x)=
\gcd(a_1+x,a_2+x-(a_1+x),\dots,a_n+x-(a_1+x))=
\gcd(a_1+x,a_2-a_1,\dots,a_n-a_1)

,

We see that only has changed. This means that it is enough for us to keep \gcd(a_2-a_1,\dots,a_n-a_1) and perform the addition operation only with a_1.

Problem Author:

Oleksandr Tymkovich

Problem Prepared by:

Oleksandr Tymkovich, Pavlo Tsytsi

Editorial by:

Oleksandr Tymkovich