Блог

Я хотел бы привести число к некоторой степени, затем умножить его на другое число и, наконец, изменить его.

Функция Python pow, которая принимает 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 из этих чисел.

Ни одно из вышеперечисленных решений на самом деле не сработало для меня, либо они были слишком медленными, либо не возвращали правильный ответ.

Ваше второе решение содержит неверное предположение о том, что верно следующее. Интуитивно понятно, что это не может быть правдой, потому что первое выражение может быть таким же большим, как 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