Notice
Recent Posts
Recent Comments
Link
«   2025/06   »
1 2 3 4 5 6 7
8 9 10 11 12 13 14
15 16 17 18 19 20 21
22 23 24 25 26 27 28
29 30
Archives
Today
Total
관리 메뉴

전공공부

[BOJ_2824] 최대공약수 본문

Study/Problem Solving

[BOJ_2824] 최대공약수

monitor 2023. 12. 1. 21:44

설명


GCD(A,B) = GCD(a,b) * GCD(a1,b1) * ...을 이용한 것인데 간과하고 풀었던 것이... GCD 한 번 해준 이후로는 거쳐간 수를 다시 나누어진 GCD의 값으로 업데이트를 시켜줘야 했는데 그렇지 않고 풀어서 다음번 GCD를 돌때 다시 큰 값으로 올라가서 이상한 숫자가 나오게 되었다. 

 

즉, GCD(A,B) = GCD(a,b) * GCD(a, 또 다른 수) *... 이런 형태가 되었던 것 

 

코드


 

package Math;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.List;
import java.util.StringTokenizer;

public class BOJ_2824 {
    static List<Integer> AList;
    static List<Integer> BList;

    public static void main(String[] args) throws IOException {
        BufferedReader in = new BufferedReader(new InputStreamReader(System.in));
        StringTokenizer tk = new StringTokenizer(in.readLine(), " ");
        int N = Integer.parseInt(tk.nextToken());
        AList = new ArrayList<>();
        BList = new ArrayList<>();
        tk = new StringTokenizer(in.readLine(), " ");
        for (int i = 0; i < N; i++) {
            AList.add(Integer.parseInt(tk.nextToken()));
        }
        tk = new StringTokenizer(in.readLine(), " ");
        int M = Integer.parseInt(tk.nextToken());
        tk = new StringTokenizer(in.readLine(), " ");
        for (int i = 0; i < M; i++) {
            BList.add(Integer.parseInt(tk.nextToken()));
        }
        long num = 1;
        boolean check = false;
        for (int i = 0; i < N; i++) {
            for (int j = 0; j < M; j++) {
                int gcd = GCD(AList.get(i), BList.get(j));
                num *= gcd;
                if(num >= 1000_000_000){
                    check = true;
                }
                num %= 1000_000_000;
                AList.set(i,(AList.get(i) / gcd));
                BList.set(j,(BList.get(j) / gcd));

            }
        }
        if(check)
        {
            System.out.printf("%09d\n", num);
        }else{
            System.out.println(num);
        }

    }

    private static int GCD(int a, int b) {
        if (b == 0) {
            return a;
        }
        return GCD(b, a % b);
    }
}
 

2824번: 최대공약수

첫째 줄에 N(1 ≤ N ≤ 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 이 수는 모두 1,000,000,000보다 작고, N개의 수를 곱하면 A가 된다. 셋째 줄에 M(1 ≤ M ≤ 1000)이

www.acmicpc.net

 

'Study > Problem Solving' 카테고리의 다른 글

[BOJ_1669] 멍멍이 쓰다듬기  (1) 2023.12.03
[BOJ_1456] 거의 소수  (2) 2023.12.02
[BOJ_9421] 소수 상근수  (1) 2023.11.30
[BOJ_2168] 타일 위의 대각선  (1) 2023.11.29
[BOJ_2553] 마지막 팩토리얼 수  (0) 2023.11.28