최대공약수
시간 제한1초메모리 제한192 MB
최대 1000개씩의 인수 리스트로 만들어지는 거대한 수 A와 B의 최대공약수를 소인수분해를 이용해 마지막 9자리로 구하는 문제입니다.
문제
두 양의 정수 A와 B가 있다. A는 주어진 N개의 양의 정수를 모두 곱한 값이고, B는 주어진 M개의 양의 정수를 모두 곱한 값이다. 두 곱은 매우 클 수 있다.
두 수열이 주어질 때, A와 B의 최대공약수를 구하시오.
입력
첫째 줄에 N(1 <= N <= 1000)이 주어진다. 둘째 줄에는 N개의 양의 정수가 공백으로 구분되어 주어진다. 각 정수는 1,000,000,000보다 작으며, 이 정수들의 곱이 A이다.
셋째 줄에 M(1 <= M <= 1000)이 주어진다. 넷째 줄에는 M개의 양의 정수가 공백으로 구분되어 주어진다. 각 정수는 1,000,000,000보다 작으며, 이 정수들의 곱이 B이다.
출력
A와 B의 최대공약수를 출력한다. 최대공약수를 10진수로 썼을 때 9자리보다 길면 마지막 9자리만 출력한다. 마지막 9자리가 0으로 시작하는 경우에도 그 0을 모두 출력한다.