백준 BOJ 2824 - 최대공약수

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

2824번: 최대공약수

GCD 응용 문제.

입력으로 들어오는 수들을 다 곱해내면 범위제한을 훌쩍 초과하게 된다.

오버플로우가 발생하는것을 막기 위해서,

입력으로 들어오는 수들에서 바로 최대공약수를 계산해야 한다.

A와 B 두 배열에 입력을 받았을 때,

두 배열에서 임의의 한쌍의 수를 뽑는데 O(N^2) 만큼이 걸리며,

이렇게 뽑아온 두 수의 최대공약수를 정답에 곱해주는 방법으로 계산하면

오버플로우 없이 최대공약수를 구할 수 있다.

 

입력받은 수들을 곱해서 A와 B라는 수들을 구성하듯이,

공약수를 조금씩 곱해서 최대공약수를 구성하는 방법이라고 생각하면

깔끔해질 듯 하다.

 

공약수들이 두번 연속으로 계산되지 않도록

어떤 두 수를 골랐을때, 최대공약수를 구하고 그 값으로 두 수를 나눠주도록 한다.

 

출력방법이 좀 까다로운편

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

vector<ll> A;
vector<ll> B;

ll gcd(ll a, ll b){
	if(b==0) return a;
	return gcd(b,a%b);
}

int main(){
	ll N,k;
	
	cin >> N;
	while(N--){
		cin >> k;
		A.push_back(k);
	}
	
	cin >> N;
	while(N--){
		cin >> k;
		B.push_back(k);
	}
	
	ll ans = 1;
	bool flag = false;
	for(int i=0; i<A.size(); i++){
		for(int j=0; j<B.size(); j++){
			ll tmp = gcd(A[i],B[j]);
			ans *= tmp;
			A[i] /= tmp;
			B[j] /= tmp;
			if(ans >= 1000000000LL) flag = true;
			ans %= 1000000000LL;
		}
	}
	
	if(flag) printf("%09d", ans);
	else printf("%d", ans);
	return 0;
}