728x90
21568번: Ax+By=C
A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자. x, y는 정수 -1,000,000,000 ≤ x, y ≤ 1,000,000,000
www.acmicpc.net
분석
확장 유클리드 알고리즘
확장 유클리드 호제법 유클리드 호제법 : 두 수의 최대 공약수 구하기 확장 유클리드 호제법 : 방정식의 해 구하기 베주 항등식 (Bezout's Identity) 의 명제를 기반으로 해를 구하는 알고리즘 베주 항
karla.tistory.com
풀이
"""
A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자.
x, y는 정수
-1,000,000,000 ≤ x, y ≤ 1,000,000,000
"""
import math
a,b,c=map(int,input().split())
def execute(a,b):
ret=[0]*2
if b==0:
ret[0]=1
ret[1]=0
return ret
q=a//b # 몫
v=execute(b,a%b) # 재귀형태로 유클리드 호제법 수행
# 역순으로 올라오면서 x,y 계산
ret[0]=v[1]
ret[1]=v[0]-v[1]*q
return ret
mgcd=math.gcd(a,b)
if c%mgcd!=0:
print(-1)
else:
mok=int(c/mgcd)
ret=execute(a,b)
print(ret[0]*mok, end=' ')
print(ret[1]*mok)
728x90