Как работает деление с остатком в pow() с отрицательной степенью?
В 3.8 добавили возможность использовать pow() с тремя аргументами при отрицательном втором аргументе. Не понял, как это работает. Объясните, пожалуйста, в максимальных подробностях.
Ответы (1 шт):
Автор решения: Stanislav Volodarskiy
→ Ссылка
Из документации про pow:
If mod is present and exp is negative, base must be relatively prime to mod. In that case, pow(inv_base, -exp, mod) is returned, where inv_base is an inverse to base modulo mod.
Пример: pow(2, -3, 17) = pow(9, 3, 17). Почему? Потому что 2 * 9 mod 17 = 18 mod 17 = 1. То есть, 9 и 2 взаимно обратные по модулю 17. 2**-1 = 9, 9**-1 = 2.
Для поиска обратного значения по модулю используется расширенный алгоритм Евклида.