Выравнивание зарядов

Просмотр в формате PDF
Submit solution
Очки: 160
Ограничение по времени: 1.0s
Ограничение по памяти: 64M
Автор:
montes332
Problem types
Allowed languages
C++, Python

На исследовательской станции хранится массив энергетических ячеек. Для каждой ячейки известен её текущий заряд a_i.

Инженеры хотят, чтобы после серии операций заряд каждой ячейки делился на k.

Разрешены следующие операции:

  • выбрать ровно одну ячейку и увеличить её заряд на текущее значение x;
  • либо пропустить ход, увеличив только значение x.

После любой операции значение x увеличивается на 1. Изначально x = 0.

Каждую ячейку разрешается изменять не более одного раза. Некоторые ячейки можно не изменять вовсе.

Для каждого набора данных определите минимальное количество операций, после которого заряд каждой ячейки будет кратен k.

Входные данные

В первой строке записано одно целое число t — количество наборов данных.

Далее следуют описания наборов данных.

Для каждого набора данных:

  • в первой строке записаны два целых числа n и k — количество ячеек и требуемый делитель;
  • во второй строке записаны n целых чисел a_1, a_2, ..., a_n — заряды ячеек.

Выходные данные

Для каждого набора данных выведите одно целое число — минимальное количество операций.

Ограничения

  • 1 <= t <= 2 * 10^4
  • 1 <= n <= 2 * 10^5
  • 1 <= k <= 10^9
  • 1 <= a_i <= 10^9
  • сумма всех n по всем наборам данных не превосходит 2 * 10^5

Пример

Входные данные
4
5 4
1 2 3 4 5
6 3
3 6 9 12 15 18
4 7
1 8 15 22
5 5
2 7 12 17 22
Выходные данные
8
0
28
24

Пояснение

В первом наборе данных некоторые элементы уже делятся на 4, а остальным нужно подобрать такие прибавления, чтобы после соответствующих операций они тоже стали кратны 4.

Во втором наборе данных все заряды уже делятся на 3, поэтому ответ равен 0.

В третьем и четвёртом наборах данных важно учитывать, что значение x после каждой операции увеличивается, поэтому одинаковые «нехватки до кратности» мешают друг другу и требуют дополнительных ходов.

Комментарии


  • 0
    Лейхнер_Константин  прокомментировал 31 Март 2026, 2:08 п.п. ← отредактирован

    .


  • 0
    Лейхнер_Константин  прокомментировал 30 Март 2026, 12:37 п.п. ← редактировать 2

    А почему в 1 наборе ответ 9? Там можно за 6 операций уложиться. 0)1 2 3 4 5->1)1 2 4 4 5->2)1 4 4 4 5->3)4 4 4 4 5->4)4 4 4 4 9->5)4 4 4 4 14->6)4 4 4 4 20. Или это я не понял условие? А код из разбора вообще пишет, что там 8


    • 1
      montes332  прокомментировал 31 Март 2026, 1:14 п.п.

      Обновил условия, там верный ответ 8