본문 바로가기

Tech/[PS] Reviews

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

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


목차

  • 문제
  • 풀이

 


문제

문제 내용

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

 

2436번: 공약수

첫째 줄에 두 개의 자연수가 빈칸을 사이에 두고 주어진다. 첫 번째 수는 어떤 두 개의 자연수의 최대공약수이고, 두 번째 수는 그 자연수들의 최소공배수이다. 입력되는 두 자연수는 2 이상 100,0

www.acmicpc.net


풀이

나의 풀이

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

해당 블로그(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);
    }
}