1. 문제 설명 📌

(1) 링크🔗

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

(2) 해설🕵

최대공약수와 최소 공배수의 관계를 알고 있는지 묻는 문제

2. 생각의 흐름: 코드가 나오기까지 🗃️

(1) IDEA 도출💡

KEY WORD: 유클리드 호제법

유클리드 호제법의 개념만 알면 문제가 쉬워서 바로 SUDO CODE로 넘어가겠다. 혹시 개념에 대해 모르시는 분들은 다음 두 개의 포스팅을 한번 읽고 오시길 바란다.

https://dalcheonroadhead.tistory.com/485

https://dalcheonroadhead.tistory.com/486

(2) SUDO CODE 📜

1️⃣ 입력으로 받은 A, B의 최대공약수 G를 구한다.
2️⃣ G 로 A,B를 나눠서 몫인 a, b를 얻는다.
3️⃣ 문제에서 원하는 LCM은 최대공약수에 각 두 수에서 나오는 서로소를 곱한 G * a * b 이다. 이를 출력한다.

(3) 시간복잡도 분석 🕓

시간복잡도를 계산할 필요가 없는 문제이다.

3. 구현 코드 🔎

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));
        int T = Integer.parseInt(br.readLine());
        for (int tc = 0; tc < T; tc++) {
            StringTokenizer st = new StringTokenizer(br.readLine());
            int A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            int G = GCD(A,B);
            int a = A/G;
            int b = B/G;
            System.out.println((G*a*b));
        }
    }

    public static int GCD(int A, int B) {
        int R = A%B;
        while (R != 0){
            A = B;
            B = R;
            R = A%B;
        }
        return B;
    }
}