2436 - 공약수(java)

Byung Seon Kang·2022년 12월 6일
0

코드

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());
        long gcd = Long.parseLong(st.nextToken());
        long lcm = Long.parseLong(st.nextToken());
        long ans1 = gcd, ans2 = lcm;
        long max = gcd * lcm;

        for (long i = 2 * gcd; i * i <= max; i += gcd) {
            if (max % i == 0) {
                long tmp = max / i;

                if (gcd(i, tmp) == gcd) {
                    if (ans1 + ans2 > i + tmp) {
                        ans1 = i;
                        ans2 = tmp;
                    }
                }
            }
        }
        System.out.println(ans1 + " " + ans2);
    }

    private static long gcd(long a, long b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
}
  • gcd * lcm = ab이다.
  • ab의 약수들을 가지고 정답을 찾으면 됨.
  • 가장 늦게 찾은 녀석이 가장 합이 작은 녀석
profile
왜 필요한지 질문하기

0개의 댓글