[BOJ 백준] 최대공약수(2824) C++

 

링크 : 

 

문제 설명 : 

상근이는 학생들에게 두 양의 정수 A와 B의 최대공약수를 계산하는 문제를 내주었다. 그런데, 상근이는 학생들을 골탕먹이기 위해 매우 큰 A와 B를 주었다.

상근이는 N개의 수와 M개의 수를 주었고, N개의 수를 모두 곱하면 A, M개의 수를 모두 곱하면 B가 된다.

이 수가 주어졌을 때, 최대공약수를 구하는 프로그램을 작성하시오.

 

입력 : 

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

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

출력 : 

두 수의 최대공약수를 출력한다. 만약, 9자리보다 길다면, 마지막 9자리만 출력한다. (최대 공약수가 1000012028인 경우에는 000012028을 출력해야 한다)

예제 입력 : 

3
358572 83391967 82
3
50229961 1091444 8863

예제 출력 : 

000012028

 

 

접근법 : 

1) 어떻게 풀 것인가?

 

2) 시간복잡도

 

 

3) 공간복잡도

 

 

4) 풀면서 놓쳤던점

 

 

5) 이 문제를 통해 얻어갈 것

 

 

 

C++ 코드 : 

// 최대공약수 2824
#if 1
#pragma warning(disable:4996)
#include <cstdio>

#define MAX (1000+3)
#define INF (1000000000)

using namespace std;

long long gcd(long long a, long long b) {
	// a > b가 되도록 swap(a,b)
	if (b > a) {
		long long  tmp = b;
		b = a;
		a = tmp;
	}

	// 유클리드 호제법
	long long  c;
	while (b) {
		c = a % b;
		a = b;
		b = c;
	}
	return a;
}

int N,M;
int A[MAX];
int B[MAX];

long long ans = 1;

bool isOver;

int main() {

	// 1. 입력
	//freopen("input.txt", "r", stdin);
	
	scanf("%d", &N);
	for (int i = 0; i < N; i++) {
		scanf("%d", &A[i]);
	}

	scanf("%d", &M);
	for (int i = 0; i < M; i++) {
		scanf("%d", &B[i]);
	}

	// 2. 이중 for문
	long long gc;
	for (int i = 0; i < N; i++) {
		for (int j = 0; j < M; j++) {

			gc = gcd(A[i], B[j]);
			
			ans *= gc;
			A[i] /= gc;
			B[j] /= gc;
			
			// 10자리 이상이면 마지막 9자리만 출력
			if (ans >= INF) { 
				ans %= INF;
				isOver = true;
			}

		}
	}

	// 3. 출력방식 조정
	if (isOver) {
		printf("%09lld", ans);
	}	
	else {
		printf("%lld", ans);
	}

	return 0;
}
#endif