Как получить остаток огромного числа?

Question

[Андрей]

У меня есть 2 переменных

N = int(input())
arr = []

N заполнена 10¹⁸
А список arr заполнен неизвестным количеством чисел, но со значением от 2 до 10¹⁰⁰

Я знаю, что можно получить остаток деления на N так

for elem in arr:
    print(elem%N)

Но у меня есть ограничение в 1 секунду, а подобная итерация огромных чисел занимает больше.
Поэтому я вывел «формулу», что если N - четное число, то остаток 0, а если нечетное, то остаток - среднее число, которое вроде как можно получить разделив N на 2.
Но то как я написал это работает не так, и выводит слишком большое число, код:

N = int (input ())
result = []
for elements in result:
    if elements%2 == 0:
        print(sum(result)/2)
    else:
        print (0)

Так вот вопрос:
Как я могу по-другому быстро получить остаток от деления с такими огромными числами как 10¹⁰⁰ и подобными?

Comments

[Модератор]

См.п.3.8

[Андрей]

Модератор, ок, заменю

[Андрей]

Возможно последний код ужасен, но у меня уже голова кругом от этих чисел, а к сути приблизиться не могу

[mayton2019]

Андрей, несколько мыслей.

1) Если это задача наподобие codewars - то смотри подсказки и модульные тесты. Они обычно содержат намёк на действующее ограничение.

2) Тут непонятно

а если нечетное, то остаток - среднее число, которое вроде как можно получить разделив N на 2.

если ты замахнулся на математику - то приведи откуда это следует. Нужен ход рассуждений. Иначе выглядит как твои фантазии.

3) Быстрое разложение на множители длинного числа (порядка 1024/2048/4096 bit) - это криптографическая задача. Она как-бы стоит на страже инфо-безопасности. Твой бенчмарк или олимпиадка - вроде-бы не достигает еще таких величин но опасно приближается. Тем более что деление-умножение по времени растет квадратично от длины числа.

[Андрей]

mayton2019,
1.
Модульных тестов нет от слова совсем.
Насчет 2 я сам не уверен будет ли это так работать, и как раз хочу узнать как мне оформить подробную формулу
Тк если итерировать такие числа через цикл, то это ооочень долго.

[Андрей]

mayton2019, у меня была рабочая версия проекта, но я упирался в ограничение по времени на исполнение(1 секунда), и единственным вариантом решить это быстрее - вывести формулу

[mayton2019]

Андрей, покажи текст оригинального задания.

[Андрей]

mayton2019,
Условие:
Есть N целых чисел. Сами числа нам неизвестны, но известно, что никакие два из этих чисел не имеют одинакового остатка при делении на N. Требуется подсчитать остаток от деления их суммы на N

А также ограничение в 1 секунду и объем занимаемой памяти 512 мб

[mayton2019]

Андрей, не знаю хитро как-то описано. И у тебя N чисел и остаток N? Одна переменная в исходных?

Попробуй арифметику по модулю. Тоесть например 6 + 6 = 2(mod 10).

По идее должно быть быстрее чем просто складывать и делить.

[Андрей]

mayton2019, да, описано хитро, но по факту код выглядит так

N = int(input())
arr =[]
for elements in arr:
    arr.append(elements%N)
print(sum(list(set(arr))))

Только этот вариант долгий

[Андрей]

mayton2019, проблемно будет обрабатывать по модулю 10 в 100 степени :)

[mayton2019]

Андрей, это фигня какая-то. Вот сложение по модулю https://ru.khanacademy.org/computing/computer-scie...

Посмотри как сделано.

[Андрей]

mayton2019, мы с одним человеком думали насчет того, как обработать такие числа быстро, и он пришел к этому , ,

[mayton2019]

Капец. Я пошел спать.

[Андрей]

mayton2019, спокойной ночи

[res2001]

Андрей,

Условие:
Есть N целых чисел. Сами числа нам неизвестны, но известно, что никакие два из этих чисел не имеют одинакового остатка при делении на N. Требуется подсчитать остаток от деления их суммы на N

Имеем N чисел в диапазоне от 0 до N-1, т.к. именно такой результат дает операция взятия остатка от деления на N. Каждое из чисел отличается от других. Это значит, что N чисел это: 0, 1, 2, 3, ..., N-1
Т.е. остатки от деления N чисел образуют арифметическую прогрессию с d = 1. При этом первый член прогрессии 0, последний член - (N-1).
Гуглим формулу суммы n членов арифметической прогрессии: Sn = (a1 + an)*n/2
Подставляем в формулу наши исходные данные, получаем: Sn = (0 + (N-1)) * N / 2 = N(N-1)/2 - это и есть сумма остатков.
Но нам нужен остаток от деления суммы остатков. Поэтому результат задачи: Sn%N
Итого: N(N-1)/2%N
hint000 победил!

Answer 1

[hint000]

Не нужно тут вообще никаких циклов, ответ сразу известен: (N*(N-1)/2)%N.
Потому что остаток от деления суммы равен остатку от деления суммы остатков - вполне очевидно.
А сумма остатков как раз и равна (N*(N-1)/2).