2824: 최대공약수

문제 보기
보자마자 계속 에라토스만 생각했는데,
지수를 char로 잡는 바람에 맞왜틀을 외쳤네요ㅠ
수가 워낙 크다보니 short 정도는 잡아줘야 한답니다..!

$\text{Solution 1})$

에라토스테네스로 적절한 전처리 후 소수판정으로 풀면 됩니다.

걸리적 거리는 처리가 존재하게 되는데, 바로 for{while{...}} 이후 if(a>1) ++pA[a]인 부분입니다.
걸어놓은 상한 $N$과 무관하게 $10^9$이하의 어떤 소수도 가능하기 때문이죠.
따라서 인덱스 범위를 설정하는 것이 불가능해집니다.

이때 도입할 것은 map 자료형입니다. 로그시간의 쿼리이지만, AC를 받기에 충분하니 unordered_map을 쓸 필요는 없습니다.

$\text{Solution 2})$

$A=a_1\times a_2\cdots\times a_n$, $B=b_1\times b_2\cdots\times b_m$로 잡고서 기저 gcd값들을 구하는 방식입니다. 물론 호제법 처리 후 나눠줘야 올바른 값을 얻을 수 있습니다.
직관적으로 떠올리기는 어려운 풀이입니다. 대신 매우 간단하니 한 번쯤 고민해봅시다.