[BOJ_2824] 최대공약수

설명

---

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번: 최대공약수