045 Ax+By=C

첫번째 코드

 

일단 백준에서는 아직 채점이 불가능한 문제이다!

 

확장 유클리드 호제법을 알고 있어야 풀 수 있는 문제라고 생각이 든다..어렵다 어려워;

한번씩 더 생각해서 코드를 구성해야 해서, 다음에 다시 또 풀어보도록 하자!

유클리드 호제법 확장.... 메모....

 

추가적인 이해와 빠른 이해 방법이 있으면 나중에 설명을 추가하자!

 

import sys
input = sys.stdin.readline

a, b, c = map(int, input().split())

def MOD(a, b):
    if b == 0:
        return a
    else:
        return MOD(b, a % b)

def euclidean (a, b):
    ret = [0] * 2
    if b == 0:
        ret[1] = 0
        ret[0] = 1
        return ret
    q = a // b
    v = euclidean(b, a % b)
    ret[0] = v[1]
    ret[1] = v[0] - v[1] * q
    return ret

divisor = MOD(a, b)

if c % divisor != 0:
    print(-1)
else:
    mok = int(c / divisor)
    ret = euclidean(a, b)
    print(ret[0] * mok, end = ' ')
    print(ret[1] * mok)