전공공부
[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번: 최대공약수
첫째 줄에 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 |