Как найти такие 2 числа в последовательности, сумма которых будет кратна m?

Question

[Антон Муравьев]

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

Upd: m != 1

Comments

[BitNeBolt]

А последовательность вводится отсортированной?

[Сергей Соколов]

сумбурно написали. Что вводится, размер чего - числа или длина последовательности - maxInt. Где ваш код для «коротких вариантов»?

[Антон Муравьев]

NeMalenKihren, Далеко не отсортированная, числа вводятся в любом порядке

[Антон Муравьев]

Сергей Соколов, Сначала вводится, логично, длина последовательности, затем сама последовательность, после число m, затем по условию.

[BitNeBolt]

С короткими вариантами код вполне легкий (обычный перебор).

А что за варианты? Не могли бы вы показать свои попытки?

[Антон Муравьев]

NeMalenKihren,

n = int(input())
x = []
for i in range(n):
    x.append(int(input()))
m = int(input())
for i in range(len(x)):
    for j in range(len(x) // 2):
        if (x[i] + x[j]) % m == 0 and i != j:
            print(x[i], x[j])

Ввод:
5
3
5
11
4
2
7
Вывод:
11 3
4 3
2 5

[Lynn «Кофеман»]

Какие ограничения на m?

[Антон Муравьев]

Алексей Тен, Вот как раз про m в условии задачи ничего не сказано. Возможно так же maxInt, хотя это просто предположение

[Антон Муравьев]

В комментариях к вопросу приложил свое решение

Answer 1

[Roman K]

Жду предложения алгоритмов / решения

Жду твоего задания на любой площадке фриланса. Заранее спасибо!

Answer 2

[Rsa97]

Создаём M списков (0..M-1). Каждое получаемое число X_i записываем в список X_i % M. Затем выводим пары из списков (0, 0), (1, M-1), (2, M-2), ... (M/2, M/2).

Comments

[Антон Муравьев]

Так, т.е в каком-то общем списке должно быть M списков? [[]] * m Так?

[Rsa97]

Антон Муравьев, Конкретную реализацию продумывайте самостоятельно. Я только дал идею возможного решения.

Answer 3

[longclaps]

Тотохен, преблема неразрешима.
Допустим, m==1. Тогда любое число (и сумма любой пары чисел) кратна m. Т.е. всего у нас maxInt*(maxInt-1)/2 пар, а ведь все их надо вывести.
зы. А еще у нас в питоне maxInt немеряный.

Comments

[Антон Муравьев]

Что ж, думаю, что создатель задачи этого не учел, т.к. у него стояло ограничение m > 0. Давайте считать, что
m != 1 что ли.

[longclaps]

Антон Муравьев, ты меня не понял (так бывает)
Допустим, m==2, у тебя в последовательности (берём по минимуму) maxInt/2 четных и maxInt/2 нечетных.
Пара четных четная, пара нечетных четная. Итого maxInt/2*(maxInt/2-1) пар. Сильно полегчало?

Answer 4

[mayton2019]

1) Поскольку в задаче нет ограничения на память - то мы можем спокойно использовать мемоизацию для хранения нужных нам ответов.
2) В процессе ввода (предполагается что ввод будет неспешный и задумчивый) чисел {n} мы строим хеш-таблицу всех возможных сочетаний пар {m(i),m(j)} где ключами будет кратность суммы этой пары. Здесь ключом будет сет чисел которые кратны этой сумме. Для простоты - табличку можно денормализовать и хранить несколько записей на 1 ключ. Например для {20,4}, будет кратность 2, 3, 4, 6, 8.
3) Еще для упрощения можно отбросить составные числа ключа (4, 6, 8) и хранить цепочку простых.
4) У этой задачи - бесконечное направление оптимизаций системы хранения этой таблицы. Зависит от дерзости автора. А он ... как видно парень очень суровый и дерзкий.

Answer 5

[BitNeBolt]

Ваша программа сверяет те элементы, которые уже сверяля раньше. Также, если последовательность состоит из одинаковых чисел, а делиться должно на 1 (к примеру), то ничего не выводится, хотя должно

Попробуйте следующие циклы:

for i in range(0, n):
    for j in range (i, n):
        if ((x[i] + x[j]) % m == 0):
            print(x[i], x[j])

Answer 6

[noqwerty]

Будем полагать, что элементы x[1],..., x[n] введенной последовательности хранятся в памяти с произвольным доступом. После ввода числа M выполняем вычисление рекуррентной последовательности y[i+1]=Mod(-M+y[g(y[i])]), где g некоторое легковычислимое отображение множества возможных значений элементов x[1],..., x[n] в множество 1,2,...,n. Далее алгоритмом Флойда определения периода находится коллизия y[i1]= y[i2]=Mod(-M+y[g(y[i2-1])]). Тогда сумма y[i1]+y[g(y[i2-1])] делится на M. Временная сложность оценивается O(Sqrt(M)) .