백준 2824번 최대공약수

<백준 2824번 최대공약수 - 마포 코딩박>

사용한 알고리즘: 에라토스테네스의 체


문제에서 N개 수의 곱 A 와 M개 수의 곱 B 의 gcd 를 묻고 있습니다.

문제풀이는 다음과 같습니다.

(1) 수는 최대 10^9이 주어지므로 에라토스테스의 체로 40000까지의 소수들을 구해줍니다. ( 어떤 수 A 는 root(A) 이상의 소수로는 나눠지지 않습니다. )

(2) map을 사용하여 N개의 수가 입력될 때 각 수들의 소인수 분해 값을 저장합니다. M개의 수가 입력될 때 이를 반복합니다. (단, 따로 저장)

(3) 구하고자 하는 값을 ans (long long)로 놓고, A의 수에대해 저장한 소인수 분해 값들을 보면서, B의 수에 대한 소인수 분해와 겹치는 만큼 ans에 곱해줍니다.

(4) 과정 (3)을 할 때, ans 가 10^9이 넘어가는지 체크해주고, 넘어간다면 이를 10^9으로 modulo 취해줍니다.

(5) 과정 (4)에서 10^9이 넘어간다고 체크된 경우 출력시 9자리까지만 출력하라는 조건에 유의해서 출력합니다. 제 경우에는 width 함수를 사용하였고, 남는 자리는 fill 함수로 0을 채워줬습니다.