Тривіально? Ріши

Використаємо властивість найбільшого спільного дільника — $$$\gcd(a,b)=\gcd(a,b-a)$$$.

Узагальнимо її на множину $$$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)$$$.

Після операції $$$+ x$$$ до всього масиву, отримуємо

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

Бачимо, що змінилось тільки $$$a_1$$$. Це означає, що нам достатньо зберігати $$$\gcd(a_2-a_1,\dots,a_n-a_1)$$$ та виконувати операцію на додавання тільки з $$$a_1$$$.

Автор задачі: | Олександр Тимкович
Задачу підготував: | Олександр Тимкович, Павло Ціцей
Розбір написав: | Олександр Тимкович