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

Тривіально? Ріши (Розбір)

Використаємо властивість найбільшого спільного дільника  — \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).

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

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.

Автор задачі:

Олександр Тимкович

Задачу підготував:

Олександр Тимкович, Павло Ціцей

Розбір написав:

Олександр Тимкович