BOJ 26601 - 가장 작은 수

June 23, 2023

약수가 $2^N$ 개를 가진다는 의미는 다음과 같다.

정수의 소인수분해 꼴이 $n=p_1^{k_1}p_2^{k_2} \cdots p_r^{k_r}$ 라고할 때,

$\tau(n)=\displaystyle \prod_{i=1}^{r}(k_i+1)$ 이다.

이것이 $2$ 의 거듭제곱 꼴이여야 하므로 $k_i$ 로 가능한 값은 $1,3,7,15,\dots$ 임을 알 수 있다.

따라서 대략 $111,222$ 까지 나오는 소수들의 위의 거듭제곱 값들 중 $N$ 이 모두 채워질 때 까지 작은것을 골라주면 된다.

구현은 우선순위큐로 했는데, 예를 들어 처음에 $2^1$ 을 넣는다면, 이제 다음에 $2^2$ 를 우선순위 큐에 추가해두는 것이다.

또한 $2^2$ 도 넣었다면 이제 $2^4$ 를 넣어주면 된다.

하나 넣을 때 마다 $2^k$ 에서 $k$ 가 $1$ 씩 증가하므로 이걸 $N$ 번 가장 작은것들을 골라서 넣어주기만 하면 된다.

You may also enjoy