이런저런 문제들 #1934: 최소공배수 [JAVA]

https://www.acmicpc.net/problem/1934

1934번: 최소공배수

 

 

---

 

 

 

 

 

문제 접근

 

 

 

 

[ 참고 ] https://st-lab.tistory.com/193, https://imkh.dev/algorithm-gcd-lcm/

 

 

최대공약수, 최소공배수 문제는 유클리드 호제법으로 풀면 빠르다.

 

1. 최대공약수를 구한다. by유클리드 호제법
2. 두 수의 곱에 최대공약수를 나누면 최소공배수이다.

 

 

 

 

 

 

 

 

 

 

코드

 

 

 

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.StringTokenizer;

public class Main {

	public static void main(String[] args) throws IOException {

		BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
		StringTokenizer st;

		int T = Integer.parseInt(br.readLine());

		StringBuilder sb = new StringBuilder();

		while (T-- > 0) {

			st = new StringTokenizer(br.readLine());

			int A = Integer.parseInt(st.nextToken());
			int B = Integer.parseInt(st.nextToken());

			sb.append(A * B / gcd(A, B)).append('\n');

		}

		System.out.println(sb);
	}

	static int gcd(int A, int B) {

		while (B != 0) {

			int R = A % B;
			A = B;
			B = R;
		}
		return A;
	}
}