Давайте скажем, что после всех операций массив будет состоять из элементов Х. Это означает, что последняя операция y + z = x + k для всех элементов массива была с y = X, z = X. Значит, что следующие элементы будут равны 2X - k, 3X - 2k, 4X - 3k, …, bX - (b - 1)k.
То есть, мы можем сказать, что a_i = bX - (b - 1)k и чуть поработав с выражением получить a_i - k = b(X - k).
На этом моменте мое решение оканчивается, так как я не имею представления, как можно быстро считать такое. Конечно, есть вариант с O(N * \sqrt{a}), однако a <= 10^{12}, N <= 2 * 10^5. В этот момент я думал что решение другое и прочел авторское, и оно значительно отличалось от моего. Однако, в комментариях я нашел человека, что сдал задачу и применил все те же шаги описанные сверху. К сожалению, подсчет ответа он описал вот так:
Я писал большой ответ и случайно удалил его. Ну крч gcd(a_i - k) = c * (X - k), дальше думай что с этим делать(подсказка: вырази b_i, и определись какой X тебе выгодный)
Грустно, но вроде прикол что мы хотим минимизировать c, так что скажем, что gcd(a_i, k) = (X - k).
То есть чтобы получить c для элемента, то мы для a_i отнимаем k и делим на gcd(a_i, k).
Получив c, мы пытаемся по минимуму его использовать, так что будем делить c на 2 и проверять на чет/нечет. И это будет ответом.
Ты посчитал \sum b_i, это количество элементов в конце, каждое действие увеличивает количество элементов на 1, а значит мы сделали \sum b_i - n действий(Так как изначально было n элементов). Это же часть твоего решения :0
А все понял, я просто когда в тетради решал обозначил как aX - bk = a_i и написал b - количество операций, но потом я заменил на (a - 1) и оно испарилось(а потом вообще я буквой b другую переменную назвал xD)
