/
xddxdd
/
Python
Обзор
Документация
Войти
/
xddxdd
/
Python
Код
Запросы
0
Задачи
Вики
Пакеты
0
Релизы
0
Аналитика
Безопасность
master
maths/fermat_little_theorem.py
30 строк
840 B
Kamil
Fermat_little_theorem type annotation (#9794)
05 окт 2023, 14:30
Не верифицирован
05 окт 2023, 14:30
0e3ea3f
Код
Авторство
О чём код?
# Python program to show the usage of Fermat's little theorem in a division # According to Fermat's little theorem, (a / b) mod p always equals # a * (b ^ (p - 2)) mod p # Here we assume that p is a prime number, b divides a, and p doesn't divide b # Wikipedia reference: https://en.wikipedia.org/wiki/Fermat%27s_little_theorem def binary_exponentiation(a: int, n: float, mod: int) -> int: if n == 0: return 1 elif n % 2 == 1: return (binary_exponentiation(a, n - 1, mod) * a) % mod else: b = binary_exponentiation(a, n / 2, mod) return (b * b) % mod # a prime number p = 701 a = 1000000000 b = 10 # using binary exponentiation function, O(log(p)): print((a / b) % p == (a * binary_exponentiation(b, p - 2, p)) % p) # using Python operators: print((a / b) % p == (a * b ** (p - 2)) % p)