[Java] 백준 2436번 : 공약수

문제

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

 

 

접근 방법

1. 최대공약수와 최소공배수가 주어지고, 최대공약수를 만족하는 두 수, 최소공배수를 만족하는 두 수를 구하는 문제이다.
2. 따라서 두 수 (A,B) / 최대공약수 = 최소공배수 이므로 A * B = 최대공약수 * 최소공배수이다.
3. 최대공약수의 배수를 탐색하며 조건에 맞게 a와 b를 찾아줍니다.

코드

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

public class Main {
    private static BufferedReader br;
    private static StringTokenizer st;
    private static long gcd,lcm;
    private static long temp;
    private static long A,B;

    //입력
    public static void input() throws Exception {
        br = new BufferedReader(new InputStreamReader(System.in));

        st = new StringTokenizer(br.readLine());
        gcd = Long.parseLong(st.nextToken());
        lcm = Long.parseLong(st.nextToken());

        temp = gcd * lcm;
        A = gcd;
        B = lcm;
    }
    
    //최대공약수
    public static long foundGCD(long x, long y){
        while(x%y != 0){
            long temp = x%y;
            x = y;
            y = temp;
        }
        return y;
    }

    //실행
    public static void process() {
        for(long i = gcd ; i*i <= temp ; i+=gcd){
            if(temp%i == 0 && foundGCD(i,temp/i) == gcd){
                long a = i;
                long b = temp/i;
                if(A+B>a+b){
                    A = a;
                    B = b;
                }
            }
        }

        System.out.println(A+" "+B);
    }


    public static void main(String[] args) throws Exception {
        input();
        process();
    }
}