1. 문제 링크
https://swexpertacademy.com/main/code/problem/problemDetail.do?contestProbId=AV-0U8FKZLQDFAXT&categoryId=AV-0U8FKZLQDFAXT&categoryType=CODE&problemTitle=3032&orderBy=FIRST_REG_DATETIME&selectCodeLang=ALL&select-1=&pageSize=10&pageIndex=1
2. 소스코드
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class Solution {
static final StringBuilder answer = new StringBuilder();
static final Reader scanner = new Reader();
static int a;
static int b;
static void input() {
a = scanner.nextInt();
b = scanner.nextInt();
}
static void solution() {
int[] result = extendedEuclidean(a, b);
if (result == null) {
answer.append(-1).append('\n');
} else {
answer.append(result[0]).append(' ').append(result[1]).append('\n');
}
}
static int[] extendedEuclidean(int a, int b) {
int r0 = a, r1 = b;
int s0 = 1, s1 = 0;
int t0 = 0, t1 = 1;
int temp = 0, q = 0;
while (r1 > 0) {
q = r0 / r1;
temp = r0;
r0 = r1;
r1 = temp - r1 * q;
temp = s0;
s0 = s1;
s1 = temp - s1 * q;
temp = t0;
t0 = t1;
t1 = temp - t1 * q;
}
if (r0 != 1) {
return null;
} else {
return new int[]{s0, t0};
}
}
public static void main(String[] args) {
int T = scanner.nextInt();
for (int testNum = 1; testNum <= T; testNum++) {
answer.append('#').append(testNum).append(' ');
input();
solution();
}
System.out.print(answer);
}
static class Reader {
BufferedReader br;
StringTokenizer st;
public Reader() {
br = new BufferedReader(new InputStreamReader(System.in));
}
String next() {
while (st == null || !st.hasMoreElements()) {
try {
st = new StringTokenizer(br.readLine());
} catch (IOException e) {
e.printStackTrace();
}
}
return st.nextToken();
}
int nextInt() {
return Integer.parseInt(next());
}
}
}
3. 접근
베주 항등식
정의
- GCD(a, b) = d라고 할 때,
1. ax + by = d 를 만족하는 정수 x, y가 존재한다.
- d는 정수 x, y에 대하여 ax + by로 표현할 수 있는 가장 작은 정수이다.
- ax + by로 표현될 수 있는 모든 정수는 d의 배수이다.
확장 유클리드 호제법
- a, b의 최대 공약수와 ax + by = gcd(a, b)를 만족하는 x, y를 구하는 알고리즘
초기 조건
- r0=a,r1=b
- s0=1,s1=0
- t0=0,t1=1
동작
- qi=ri−1/ri
- ri=ri−2−ri−1qi
- si=si−2−si−1qi
- ti=ti−2−ti−1qi