약수 개수 / 약수 합

이 글에서는 주어진 정수 $n$에 대해 약수 개수 $d(n)$와 약수 합$\sigma(n)$을 계산하는 방법에 대해 다룬다.

약수 개수

약수 $d$의 소인수분해는 당연히 $n$의 소인수분해에 포함되어야 한다. 예를 들어, $6 = 2 \cdot 3$은 $60 = 2^2 \cdot 3 \cdot 5$의 약수이다. 따라서 $n$의 소인수분해가 갖는 서로 다른 부분집합을 모두 찾으면 약수 개수 문제를 해결할 수 있다.

일반적으로 원소가 $x$개인 집합은 $2^x$개의 부분집합을 갖는다. 그러나 집합에 중복되는 원소가 있으면 이 사실은 적용할 수 없다. 이 문제의 경우 $n$의 소인수분해에서 어떤 소인수는 여러번 등장할 수 있다.

소인수 $p$가 $n$의 소인수분해에서 $e$번 등장한다고 하면, 부분집합을 구성할 때 $p$를 최대 $e$개까지 사용할 수 있는 셈이고, 선택의 경우의 수는 $(e + 1)$이 된다.

따라서, 소수 $p_i$에 대해 $n$의 소인수 분해가 $p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$일 때, $n$의 약수 개수는

이다.

이에 대한 사고방식은 다음과 같다:

• 만약 소인수가 한 가지 존재하여 $n = p_1^{e_1}$인 경우, $n$의 약수는 $1, p_1, p_1^2, \dots, p_1^{e_1}$으로 $(e_1 + 1)$개 존재한다.

• 만약 소인수가 두 가지 존재하여 $n = p_1^{e_1} \cdot p_2^{e_2}$인 경우, 다음 표를 사용해 모든 약수를 나열할 수 있다.

  $$\begin{array}{c|ccccc} & 1 & p_2 & p_2^2 & \dots & p_2^{e_2} \\ \hline 1 & 1 & p_2 & p_2^2 & \dots & p_2^{e_2} \\ p_1 & p_1 & p_1 \cdot p_2 & p_1 \cdot p_2^2 & \dots & p_1 \cdot p_2^{e_2} \\ p_1^2 & p_1^2 & p_1^2 \cdot p_2 & p_1^2 \cdot p_2^2 & \dots & p_1^2 \cdot p_2^{e_2} \\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\ p_1^{e_1} & p_1^{e_1} & p_1^{e_1} \cdot p_2 & p_1^{e_1} \cdot p_2^2 & \dots & p_1^{e_1} \cdot p_2^{e_2} \\ \end{array}$$

  약수 개수는 $(e_1 + 1) \cdot (e_2 + 1)$이다.

• 두 가지 이상의 서로 다른 소인수가 있는 경우에도 비슷하게 논증할 수 있다.

약수 합

이전 절에서 사용했던 논증을 다시 사용할 수 있다.

• 만약 소인수가 한 가지 존재하여 $n = p_1^{e_1}$인 경우, 합은 다음과 같다:

  $$1 + p_1 + p_1^2 + \dots + p_1^{e_1} = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1}$$

• 만약 소인수가 두 가지 존재하여 $n = p_1^{e_1} \cdot p_2^{e_2}$인 경우, 이전과 같이 약수를 표로 나열할 수 있다. 한 가지 차이점은, 이제 표에 나온 약수 개수를 세는 대신 약수를 모두 더하려고 한다는 것이다. 각 조합의 합을 다음과 같이 표현할 수 있다.

  $$\left(1 + p_1 + p_1^2 + \dots + p_1^{e_1}\right) \cdot \left(1 + p_2 + p_2^2 + \dots + p_2^{e_2}\right)$$
  $$= \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1}$$

• 일반적으로 $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$인 경우, 다음 공식을 얻는다.

  $$\sigma(n) = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1} \cdots \frac{p_k^{e_k + 1} - 1}{p_k - 1}$$

곱셈적 함수

곱셈적 함수(multiplicative function)는 서로소인 $a$, $b$에 대해

를 만족하는 함수 $f$이다.

약수 개수 함수 $d(n)$와 약수 합 함수 $\sigma(n)$는 곱셈적 함수이다.

곱셈적 함수는 정수론 문제에서 아주 유용한 성질을 많이 가지고 있다. 예를 들어, 두 곱셈적 함수의 디리클레 합성곱은 다시 곱셈적 함수가 된다.

연습문제

• SPOJ - COMDIV
• SPOJ - DIVSUM
• SPOJ - DIVSUM2