백준_21568 Ax+By=C (확장 유클리드 호제법)Algorithm/Algorithm 문제2024. 2. 10. 23:30
Table of Contents
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;
public class BJ_21568_AxByC {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
StringTokenizer st = new StringTokenizer(br.readLine(), " ");
StringBuilder sb = new StringBuilder();
int a = Integer.parseInt(st.nextToken());
int b = Integer.parseInt(st.nextToken());
int c = Integer.parseInt(st.nextToken());
int gcd = gcd(a, b);
if(c%gcd != 0) {
sb.append(-1);
} else {
int[] ret = excute(a, b);
sb.append(ret[0] * (c/gcd)).append(' ');
sb.append(ret[1] * (c/gcd)).append(' ');
}
System.out.println(sb);
}
static int[] excute(int a, int b) {
if (b==0) {
return new int[]{1, 0};
}
int[] ret = excute(b, a%b);
int x = ret[1];
int y = ret[0] - (ret[1]*a/b);
return new int[]{x, y};
}
static int gcd(int a, int b) {
if (b==0) {
return a;
}
return gcd(b, a%b);
}
}
'Algorithm > Algorithm 문제' 카테고리의 다른 글
백준_1325 효율적인 해킹 (BFS) (0) | 2024.02.13 |
---|---|
백준_18352 특정 거리의 도시 찾기 (BFS) (0) | 2024.02.11 |
백준_1850 최대공약수 (유클리드 호제법) (0) | 2024.02.07 |
백준_1934 최소공배수 (유클리드 호제법) (1) | 2024.02.06 |
백준_11689 GCD(n, k) = 1 (오일러 피 함수) (0) | 2024.02.05 |
@kjyyjk :: 녕의 학습 기록
포스팅이 좋았다면 "좋아요❤️" 또는 "구독👍🏻" 해주세요!