공약수2436

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

최대공약수6, 최소공배수180 을 만족하는 숫자 조합을 적어보다가 규칙을 발견하였다
숫자를 하나 만들어서 증가시키면서 6에는 곱하고 180에서는 나누면 숫자 조합이 만들어진다
그래서 이방식을 사용해서 코드를 짰는데 틀렸다고 한다
알고보니 숫자조합을 만든 뒤에 이 숫자조합의 최대공약수가 6인지 최소공배수가180인지 확인하는 코드도 필요하였다

두숫자의 최대공약수 구하는방법

두 숫자의 최대공약수(GCD)를 구하는 가장 흔한 방법은 유클리드 알고리즘이며, 자바로는 다음과 같이 구현할 수 있습니다:

java

public class Main {
    public static void main(String[] args) {
        int num1 = 48;
        int num2 = 18;
        System.out.println("GCD of " + num1 +" and " + num2 + " is " + gcd(num1, num2));
    }

    public static int gcd(int num1, int num2) {
        if (num2 == 0) {
            return num1;
        }
        return gcd(num2, num1 % num2);
    }
}

두 숫자의 최소공배수(LCM)를 구하려면 먼저 최대공약수(GCD)를 찾아야 합니다. 그리고 두 숫자의 곱을 최대공약수로 나누면 최소공배수를 얻을 수 있습니다.

다음은 자바로 이 과정을 구현한 코드입니다:

java

public class Main {
    public static void main(String[] args) {
        int num1 = 60;
        int num2 = 48;
        System.out.println("LCM of " + num1 +" and " + num2 + " is " + lcm(num1, num2));
    }

    public static int gcd(int num1, int num2) {
        if (num2 == 0) {
            return num1;
        }
        return gcd(num2, num1 % num2);
    }

    public static int lcm(int num1, int num2) {
        return (num1 * num2) / gcd(num1, num2);
    }
}

import java.io.*;
import java.util.*;
public class Main {
    public static void main(String[] args)throws IOException{

        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        String[] input = br.readLine().split(" ");
        int A = Integer.parseInt(input[0]);//최대공약수 2 ~ 1억
        int B = Integer.parseInt(input[1]);//최소공배수 2 ~ 1억

        int num = 1;
        long na = 0;
        long nb = 1;

        long minSum = Integer.MAX_VALUE;
        long mina = 0;
        long minb = 0;

        while(na < nb) {

            na = A*num;
            nb = B/num;

            if(A != gcd(na, nb)){
                num++;
                continue;
            }


            if(B != lcm(na, nb, A)){
                num++;
                continue;
            }


            if(minSum > (na+nb)){
                minSum = na+nb;
                mina = na;
                minb = nb;
            }

            num++;
        }

        System.out.println(mina + " " + minb);
    }

    public static long gcd(long a, long b){
        long min = Math.min(a,b);
        long max = Math.max(a,b);

        if(max%min == 0){
            return min;
        }else{
            return gcd(min, max%min);
        }
    }

    public static long lcm(long a, long b, int gcd){
        return (a*b)/gcd;
    }
}