В 3.8 добавили возможность использовать pow() с тремя аргументами при отрицательном втором аргументе. Не понял, как это работает. Объясните, пожалуйста, в максимальных подробностях.
1 ответ
Из документации про 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
.
Для поиска обратного значения по модулю используется расширенный алгоритм Евклида.