Day-13 확장 유클리드 호제법
1. 확장 유클리드 호제법 확장 유클리드 호제법은 방정식의 해를 구하기 위해 사용된다. 해를 구하고자 하는 방정식은 ax + by = c 이다. 위 방정식은 c가 a, b의 최대 공약수의 배수인 경우에만 정수해를 가진다. 즉, c의 최솟값이 GCD(a, b)이다. 2. 확장 유클리드 호제법 구현 a와 b의 최대 공약수를 구해 c를 gcd로 둔다. a, b로 유클리드 호제법을 반복 실행하며 몫과 나머지를 저장한다. 나머지가 0이 될 때까지 반복한다. 반복으로 구한 나머지와 몫을 이용하여 x = y', y = x' - y' * q를 계산한다. x', y'는 이전 x, 이전 y를 의미하고, q는 현재 보고 있는 몫을 의미한다. 처음 시작하는 x, y는 x', y'를 1, 0으로 설정한다. 구한 x, y에 c를..
2024. 4. 6.
[21568] Ax+By=C (JAVA)
# 문제 설명 A, B, C가 주어졌을 때, Ax+By=C를 만족하는 (x, y)중에서 다음을 만족하는 것을 아무거나 찾아보자. x, y는 정수 1,000,000,000 ≤ x, y ≤ 1,000,000,000 입력 첫째 줄에 정수 A, B, C가 주어진다. 출력 Ax+By=C를 만족하는 x, y를 공백으로 구분해 출력한다. 문제의 조건을 만족하는 (x, y)가 존재하지 않는 경우에는 -1을 출력한다. # 정답 코드 import java.io.*; import java.util.*; public class Main { public static void main(String[] args) throws IOException { BufferedReader br = new BufferedReader(new In..
2024. 4. 6.
