백준 14565번: 역원(Inverse) 구하기

문제

문제 바로가기> 백준 14565번: 역원(Inverse) 구하기

풀이

덧셈의 경우에 역원은 간단하다. 곱셈의 경우에는 최대 공약수 뿐만 아니라 역원까지 구해줄 수 있는 확장 유클리드 알고리즘을 이용하여 풀었다.

n, a = map(int, input().split())
d0, d1 = a, n
x0, x1 = 1, 0
while(d1):
    q = d0//d1
    tmp=d0
    d0=d1
    d1=tmp-q*d1

    tmp=x0
    x0=x1
    x1=tmp-q*x1
    
if d0==1:
    if x0<=0:
        x0+=n
    print(n-a, x0)
else:
    print(n-a, -1)