7089 : 확장 유클리드
•시간제한: 2.000 S
•메모리제한: 256 MB
•제출: 0
•통과: 0
•만든사람: suakii
문제 설명
확장 유클리드 알고리즘(Extended Euclidean Algorithm)은
두 자연수 a, b가 주어질 때, 이들의 최대공약수 gcd(a, b)와 함께 위 방정식을 만족하는 정수 x, y 중 하나를 구하십시오.
[제약 조건]
• 두 자연수 $a, b$: $1 \le a, b \le 10^9$
ax + by = gcd(a, b)를 만족하는 정수 x, y를 구하는 방법입니다.두 자연수 a, b가 주어질 때, 이들의 최대공약수 gcd(a, b)와 함께 위 방정식을 만족하는 정수 x, y 중 하나를 구하십시오.
[제약 조건]
• 두 자연수 $a, b$: $1 \le a, b \le 10^9$
입력 설명
첫째 줄에 두 자연수 $a$와 $b$가 공백으로 구분되어 주어집니다. ($1 \le a, b \le 10^9$)
출력 설명
최대공약수 $g$와 방정식 $ax + by = g$를 만족하는 정수해 $x, y$를 공백으로 구분하여 출력합니다.
입력 예시
COPY
복사되었습니다!
복사되었습니다!
12 15
출력 예시
COPY
복사되었습니다!
복사되었습니다!
3 -1 1도움
재귀 함수
extgcd(a, b)가 (g, x1, y1)을 반환할 때, x = y1, y = x1 - (a // b) * y1 로 갱신하여 구할 수 있습니다.