Використаємо властивість найбільшого спільного дільника — \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).
Після операції до всього масиву, отримуємо
,
Бачимо, що змінилось тільки a_1. Це означає, що нам достатньо зберігати \gcd(a_2-a_1,\dots,a_n-a_1) та виконувати операцію на додавання тільки з a_1.
Автор задачі: | Олександр Тимкович |
Задачу підготував: | Олександр Тимкович, Павло Ціцей |
Розбір написав: | Олександр Тимкович |