개발블로그by페페

2회 반복하면 나머지는 동일하다

// Operating GCD(1/2) long GCD = GCD(Math.max(A, B), Math.min(A, B)); // External Module(1/2) private static long GCD(long B, long S) { long r = B % S; while (r != 0) { r = B%S; B = S; S = r; } return Math.abs(B); }

Ax + By = C 방정식의 해를 구하는 것 - C % GCD(A, B) = 0인 경우에만 정수해를 가진다 (나누어 떨어질 때) - C의 최솟값은 1임을 적용하여 중간에서 MOD 연산 시작 예제 : 5x + 9y = 2 > 5x + 9y = 1 에서 시작 - 나머지가 0이 될때까지 연산 시행 MOD Remainder Quotient 5 % 9 = 5 5 0 9 % 5 = 4 4 1 5 % 4 = 1 1 1 4 % 1 = 0 0 4 - 최하단에서 역순으로 올라가며 x와 y 쌍 계산 x = 이전y y = 이전x - 이전y*Quotient * 최하단은 이전 값이 없으므로 이전값을 (1, 0)으로 지정 - 이렇게 재귀 형식으로 구해진 최종 (x, y)는 Ax + By = GCD(A, B)를 만족 - 또한 앞에..

- 두 수의 Greatest Common Divisor를 구하는 것 - MOD 연산 10 MOD 4 = 2 10 % 4 = 2 큰 수를 작은 수로 나누는 것 - 앞 단계의 작은 수와 remainder로 MOD 연산 재귀적으로 반복 - remainder == 0일 때 그 연산의 작은 수 = GCD

// Input Supply Cable Scanner sc = new Scanner(System.in); BufferedWriter bw = new BufferedWriter(new OutputStreamWriter(System.out)); // Preprocessing long A = sc.nextLong(); long B = sc.nextLong(); // Operating GCD long result = GCD(A, B); // Ouput Extracting Cable while (result > 0) { bw.write("1"); result--; } bw.flush(); bw.close(); 일반적인 출력을 수행하면 시간 초과가 발생할 수 있으므로 BufferedWriter를 사용합니다 *Buf..

import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { // Input Supply Cable Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int i = 0; i < T; i++) { // Preprocessing int A = sc.nextInt(); int B = sc.nextInt(); // Operating LCM int result = A*B / GCD(A, B); // Output Extracting Cable System.out.println(result); } } // External Modu..

import java.util.Scanner; public class Main { public static void main(String[] args) throws Exception { // Input Supply Cable Scanner sc = new Scanner(System.in); int T = sc.nextInt(); for (int i = 0; i < T; i++) { // Preprocessing int A = sc.nextInt(); int B = sc.nextInt(); // Operating LCM int result = A*B / GCD(Math.max(A, B), Math.min(A, B)); // Output Extracting Cable System.out.println(res..

-