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
,
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 |