Как найти такие 2 числа в последовательности, сумма которых будет кратна m? Вводится последовательность из чисел огромной длины (размер может достигать maxInt), нужно вывести максимально быстро (ограничение 1 секунда) такие 2 числа, сумма которых будет кратна какому-либо вводимому m (если таких несколько, то вывести каждую пару). Сами числа так же могут достигать maxInt. Сложность заключается лишь в том, что последовательность очень длинная. С короткими вариантами код вполне легкий (обычный перебор). Жду предложения алгоритмов / решения. Заранее спасибо!
Upd: m != 1

Предыдущий
вопрос Следующий
вопрос

Один из возможных вариантов решения данной задачи - использование хэш-таблицы для хранения остатков от деления чисел в последовательности на m.

Создать хэш-таблицу (ассоциативный массив), где ключами будут остатки от деления чисел на m, а значениями - список пар чисел, которые дали такой остаток.Проходить по каждому числу в последовательности и добавлять его в соответствующий список в хэш-таблице.Для каждого числа в последовательности находить пару, сумма которых даст остаток, равный m.Печатать найденные пары.

Пример кода на Python:

from collections import defaultdict
def find_pairs(sequence, m):
hash_table = defaultdict(list)
pairs = []
for num in sequence:
remainder = num % m
hash_table[remainder].append(num)
for key in hash_table.keys():
if key == 0 or key == m // 2:
pairs.extend([(num1, num2) for num1 in hash_table[key] for num2 in hash_table[key] if num1 != num2])
elif key < m / 2 and m - key in hash_table:
pairs.extend([(num1, num2) for num1 in hash_table[key] for num2 in hash_table[m - key]])
return pairs
# Ввод последовательности и m
sequence = list(map(int, input().split()))
m = int(input())
pairs = find_pairs(sequence, m)
for pair in pairs:
print(pair[0], pair[1])

Этот алгоритм имеет сложность O(n), где n - количество чисел в последовательности. Мы проходим по каждому числу один раз, добавляя его в хэш-таблицу, и затем ищем пары чисел для каждого элемента в хэш-таблице.