Длиннейший подотрезок с суммой, кратной k

1. Идея

Нужно найти самый длинный непрерывный отрезок массива, сумма элементов на котором делится на k.

Классическая идея здесь — использовать префиксные суммы по модулю k.

Пусть pref[i] — сумма первых i элементов, взятая по модулю k.

Тогда сумма на отрезке от l до r равна:

a[l] + a[l+1] + ... + a[r] = pref[r] - pref[l-1]

Эта сумма кратна k тогда и только тогда, когда остатки pref[r] и pref[l-1] равны.

Значит, задача сводится к следующему:

• для каждого остатка от деления префиксной суммы на k
• запомнить его самое первое появление
• если такой остаток встретился снова, то между этими позициями находится отрезок с суммой, кратной k

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

2. Наблюдения

Наблюдение 1. Равные остатки дают подходящий отрезок

Если

• pref[i] % k == pref[j] % k
• и i < j

то сумма элементов с позиции i + 1 по j делится на k.

Почему?

Потому что разность двух чисел с одинаковым остатком при делении на k кратна k.

Наблюдение 2. Нужно хранить первое появление остатка

Если остаток r встретился на позициях p1, p2, p3, ...

то для самой большой длины выгодно брать самый левый индекс p1 и самый правый текущий индекс.

Например, если сейчас остаток r встретился на позиции i, то лучший отрезок с этим остатком начинается после самой первой позиции, где этот остаток был.

Наблюдение 3. Нужно заранее добавить остаток 0 на позиции 0

Префикс длины 0 имеет сумму 0, значит его остаток тоже 0.

Это позволяет автоматически учитывать отрезки, начинающиеся с первого элемента.

Например, если сумма первых i элементов кратна k, то pref[i] == 0, и тогда длина такого отрезка будет i - 0 = i.

Наблюдение 4. Отрицательные числа не мешают

Элементы массива могут быть отрицательными, поэтому при обновлении остатка в C++ нужно следить, чтобы он оставался в диапазоне от 0 до k - 1.

В эталонном решении это делается так:

pref = (pref + a[i - 1]) % k;
if (pref < 0) pref += k;

В Python оператор % для положительного k уже даёт неотрицательный остаток, поэтому дополнительная коррекция не нужна.

3. Алгоритм

1. Считать n, k и массив a.
2. Создать словарь first_pos, где:
   • ключ — остаток префиксной суммы по модулю k
   • значение — первая позиция, где этот остаток встретился
3. Изначально записать first_pos[0] = 0.
4. Идти по массиву слева направо и поддерживать текущий остаток префиксной суммы pref.
5. Для каждой позиции i от 1 до n:
   • обновить pref
   • если такой остаток уже был:
     • длина подходящего отрезка равна i - first_pos[pref]
     • обновить ответ
   • иначе:
     • запомнить эту позицию как первую для данного остатка
6. Вывести найденный максимум.

4. Почему это работает

Докажем корректность.

Рассмотрим текущую позицию i. Пусть остаток суммы первых i элементов равен r.

Случай 1. Остаток r раньше не встречался

Тогда пока нельзя построить отрезок, заканчивающийся в i, через более ранний префикс с тем же остатком.
Но эту позицию полезно сохранить как первую для остатка r, потому что в будущем этот остаток может встретиться снова.

Случай 2. Остаток r уже встречался раньше на позиции p

Это значит, что:

• сумма первых i элементов даёт остаток r
• сумма первых p элементов тоже даёт остаток r

Тогда разность этих сумм, то есть сумма элементов с p + 1 по i, кратна k.

Следовательно, найден корректный отрезок длины i - p.

Почему достаточно хранить только первую позицию?

Пусть остаток r встречался на позициях p1 < p2 < ... < pm, и сейчас мы находимся в позиции i.

Все отрезки, заканчивающиеся в i и дающие сумму, кратную k, имеют длины:

• i - p1
• i - p2
• ...
• i - pm

Максимальная из них — i - p1, потому что p1 минимален.

Значит, для каждого остатка нужно хранить именно самое первое появление.

Почему алгоритм находит глобальный максимум?

Алгоритм перебирает все правые границы i от 1 до n.

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

Затем берётся максимум по всем i.

Следовательно, итоговый ответ — длина самого длинного непрерывного периода, сумма на котором кратна k.

5. Сложность

Пусть n — длина массива.

• Время: O(n) в среднем, так как для каждой позиции выполняется константное число операций со словарём.
• Память: O(n) в худшем случае, если все остатки префиксных сумм различны.

6. Код на C++17

#include <iostream>
#include <vector>
#include <unordered_map>
using namespace std;

int main() {
    int n;
    long long k;
    cin >> n >> k;

    vector<long long> a(n);
    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    unordered_map<long long, int> first_pos;
    first_pos[0] = 0;

    long long pref = 0;
    int answer = 0;

    for (int i = 1; i <= n; i++) {
        pref = (pref + a[i - 1]) % k;
        if (pref < 0) pref += k;

        auto it = first_pos.find(pref);
        if (it != first_pos.end()) {
            int len = i - it->second;
            if (len > answer) answer = len;
        } else {
            first_pos[pref] = i;
        }
    }

    cout << answer << '\n';
    return 0;
}

7. Код на Python 3

n, k = map(int, input().split())
a = list(map(int, input().split()))

first_pos = {0: 0}
pref = 0
answer = 0

for i in range(1, n + 1):
    pref = (pref + a[i - 1]) % k
    if pref in first_pos:
        length = i - first_pos[pref]
        if length > answer:
            answer = length
    else:
        first_pos[pref] = i

print(answer)