@AndreyJoestar

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

У меня есть 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¹⁰⁰ и подобными?
  • Вопрос задан
  • 861 просмотр
Решения вопроса 1
hint000
@hint000
у админа три руки
Не нужно тут вообще никаких циклов, ответ сразу известен: (N*(N-1)/2)%N.
Потому что остаток от деления суммы равен остатку от деления суммы остатков - вполне очевидно.
А сумма остатков как раз и равна (N*(N-1)/2).
Ответ написан
Комментировать
Пригласить эксперта
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Войти через центр авторизации
Похожие вопросы