[백준-정수론] 2436 공약수

Hi, There!
안녕하세요, 바오밥입니다.

---

목차

• 문제
• 풀이

 

---

문제

문제 내용

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

2436번: 공약수

---

풀이

나의 풀이

- 정수론 유형의 문제가 많이 약하다는 것을 느꼈다.

해당 블로그(https://velog.io/@gandi0330/Java-%EB%B0%B1%EC%A4%80-%EA%B3%B5%EC%95%BD%EC%88%98-2436%EB%B2%88)를 참고하여 풀이했다.

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 = new StringTokenizer(br.readLine());
        int gcdNum = Integer.parseInt(st.nextToken());
        int lcmNum = Integer.parseInt(st.nextToken());
        long mul = (long)gcdNum*lcmNum;

        int a = 0, b = 0;
        for(int i=gcdNum; i<=Math.sqrt(mul); i+=gcdNum) {
            if(mul % i == 0 && gcd(i, mul/i) == gcdNum) {
                a = i;
                b = (int)(mul/i);
            }
        }

        System.out.printf("%d %d", a, b);
    }

    public static long gcd(long a, long b) {
        long r = a % b;
        return r == 0 ? b : gcd(b, r);
    }
}