pow(a, b, m): быстрое возведение в степень по модулю

В олимпиадных задачах ответ часто просят «по модулю 10^9 + 7». Писать 3 ** n % M — плохая идея: Python сначала честно построит всё 3 в степени n и лишь потом возьмёт остаток. У встроенной pow есть третий аргумент — модуль. Тогда остаток берётся после каждого умножения, и промежуточные числа не растут. M = 10**9 + 7 print(pow(3, 10**18, M)) # 246336683 print(pow(3, -1, M)) # 333333336, ведь 3 * 333333336 % M == 1 Внутри — бинарное возведение в степень: основание каждый шаг возводится в квадрат и домножается в ответ, когда очередной бит показателя равен 1. Шагов около log2(b): для 10^18 это примерно 60, а не 10^18. В нашем запуске на Python 3.13 pow(3, 10**6, M) занял порядка микросекунды, а 3 ** 10**6 % M — около 50 мс: промежуточное число весит 1,58 млн бит. Отрицательная степень (Python 3.8+) даёт обратный элемент по модулю — так делят по модулю, например в C(n, k). Работает, только если a и m взаимно просты: pow(2, -1, 4) бросает ValueError. Когда брать: степени, комбинаторика и хеши по модулю. Когда не брать: дробные числа — с float третий аргумент не принимается (TypeError). источник: #шпаргалка