두 자연수 A와 B를 정한 후, Ax + By = 1이 되는 x와 y를 계산하는 프로그램을 작성하시오
12345와 123의 최대공약수를 구해보자
즉 a를 b로 나눈 나머지가 r이라했을 때 GCD(a,b) = GCD(b,r)을 이용하여 구현한 것이다.
일단 초기값으로 x1 = 1, y1 = 0, x2= 0, y2 = 1로 초기화 한다.
그리고 유클리드 호제법으로 구한 나머지들을 세팅한다.
12345 - 123x100 = 45이다. 따라서 1 + (0x-100), 0 + (1x-100)을 세팅한다.
123 - 45x2 = 33이다. 따라서 0 + (1x-2), 1 + (-100x-2)를 세팅한다. 이렇게 가다가 gcd = 3일 때 해당 x,y값을 리턴해주면 된다.
재귀구조를 사용한 유클리드 호제법이다. GCD(a,b) = GCD(b, R(a mod b))값을 이용한 것이다. 그리고 mod값을 stack에 넣어준다.
문제에서 정의한 일차 함수를 정의한다.
위에서 초기값으로 x1, y1 = 1, 0을 x2,y2 = 0, 1값으로 세팅한 것을 볼 수 있다. 그리고 해당 알고리즘을 코드로 나타내었다.
reverse여부에 따라 출력을 한다.
T = int(input())
# 여러개의 테스트 케이스가 주어지므로, 각각을 처리합니다.
for test_case in range(1, T + 1):
a, b = map(int, input().split(" "))
stack = []
reverse = False
if a < b:
tmp = a
a = b
b= tmp
reverse= True
def gcd(a, b):
if a % b == 0:
return b
stack.append(a % b)
return gcd(b, a%b)
def graph(x, y):
return a*x + b*y
x1,y1 = 1, 0
x2, y2 = 0, 1
gcd = gcd(a,b)
while True:
target = stack.pop(0)
num1 = graph(x1, y1)
num2 = graph(x2, y2)
plus = (target - num1) // num2
tmp1, tmp2 = x1 + (x2 * plus), y1 + (y2 * plus)
x1, y1 = x2, y2
x2, y2 = tmp1, tmp2
if target == gcd:
break
if not reverse:
print("#" + str(test_case) + " " + str(x2) + " " + str(y2))
else:
print("#" + str(test_case) + " " + str(y2) + " " + str(x2))