Как ловить и модифицировать гигантские числа
Я хотел бы возвести число в некоторую степень, затем умножить его на другое число и, наконец, изменить его.
Функция pow Python, которая принимает 3 параметра, не может использоваться для моего сценария использования, поэтому я пытаюсь найти быструю альтернативу.
Примеры:
я знаю, что могу сделать
9^10%2
так как
pow(9, 10, 2)
но я не могу сделать
(8*9^10)%2
с той же функцией
Я уже пытался использовать (цифры только для справки, реальные цифры намного больше)
pow(9, 10)*8 % 2 # tooks too long
pow(9, 10, 2)*8 # returns wrong answer
Я бы хотел, чтобы мои числа вычислялись очень быстро, даже если они не превышают 10^18. Мое требование времени составляет 2 секунды для 20 из этих чисел.
Ни одно из вышеперечисленных решений мне не подошло, либо они были слишком медленными, либо не давали правильный ответ.
Ответы 1
Ваше второе решение содержит неверное предположение о том, что верно следующее. Интуитивно это не может быть правдой, потому что первое выражение может быть таким же большим, как c*(n-1), но второе должно быть строго меньше n
((a^b)%n)*c == (c*a^b))%n
Правильное удостоверение от Википедия:
ab mod n = [(a mod n)(b mod n)] mod n.
Мы можем обобщить это по индукции (доказательство оставляем читателю в качестве упражнения):
Таким образом, ваше выражение должно быть:
(pow(9, 10, 2) * (8 % 2)) % 2
# OR
(pow(9, 10, 2) * 8) % 2