2

Обратное число Даны два целых числа 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)
10
  • Приведите, пожалуйста, свой код, покажите - в чём не можете конкретно разобраться...
    – DeNRuDi
    10 июн 2020 в 22:07
  • 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)
    – fox_price
    10 июн 2020 в 22:23
  • У меня не проходит по времени
    – fox_price
    10 июн 2020 в 22:26
  • зачем pow 2 раза?
    – eri
    10 июн 2020 в 22:27
  • У условия убрать pow?
    – fox_price
    10 июн 2020 в 22:29

1 ответ 1

3

Решение с использованием расширенного алгоритма Евклида. Способ через степень требует вычисления функции Эйлера. 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)

Ваш ответ

Нажимая на кнопку «Отправить ответ», вы соглашаетесь с нашими пользовательским соглашением, политикой конфиденциальности и политикой о куки

Всё ещё ищете ответ? Посмотрите другие вопросы с метками или задайте свой вопрос.