ЕГЭ №27: число пар с суммой, кратной K, за O(n)

Дан список целых чисел nums и число k. Нужно посчитать количество пар индексов i < j, для которых сумма nums[i] + nums[j] кратна k.

Наивное решение перебирает все пары за O(n^2). Требуется эффективное решение за O(n + k): подсчитать, сколько чисел даёт каждый остаток по модулю k, а затем скомбинировать остатки r и k - r (отдельно обработав остаток 0 и, при чётном k, остаток k/2).

Функция count_pairs_div(nums, k) возвращает целое число — количество подходящих пар.

Вход: nums — список целых чисел (может быть пустым); k >= 1. Выход: целое неотрицательное число.

Примеры:

count_pairs_div([1, 2, 3, 4, 5], 3) -> 4
count_pairs_div([3, 6, 9], 3)       -> 3
count_pairs_div([1, 1, 1, 1], 2)    -> 6