Обратное число к а по модулю m

Question

Обратное число Даны два целых числа m и a. Если не существует обратного числа к a по модулю m, то выведите число −1, а если существует, то выведите это число (ответ должен лежать в границах от 0 до m−1).

Входные данные В единственной строке входных данных даны два целых числа 1

Выходные данные Выведите ответ на задачу.

Примеры Ввод 179 57 Вывод 22

b = 0 
a = list(map(int, input().split())) 
b = pow(a[1], a[0] - 2, a[0]) 
if pow(a[1], a[0] - 2, a[0]) == 0: 
    print(-1) 
else: 
    print(b)

Answer 1

Решение с использованием расширенного алгоритма Евклида. Способ через степень требует вычисления функции Эйлера. e-maxx

def gcdExtended(a, b):
    if a == 0 :
        return b,0,1
    gcd,x1,y1 = gcdExtended(b%a, a)
    x = y1 - (b//a) * x1
    y = x1
    return gcd,x,y

m, a = map(int, input().split())
gcd, x, y = gcdExtended(a, m)
if gcd == 1:
    print((x % m + m) % m)
else:
    print(-1)

Answer 2

Код из ответа можно улучшить, потому что:

(x % m + m) % m = x % m

обозначим y = x % m, тогда y = y + m (mod m),

Заметим, что 0 <= y < m, а неотрицательные числа меньшие m всегда дают в остатке сами себя,
то есть y % m = y, из этого мы и получаем равенство выше.

БЛОГ НА HUSL

Обратное число к а по модулю m

Ответы (2 шт):