약수의 개수 / 약수의 합¶

이 글에서는 주어진 수 $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$가지 있습니다.

따라서 $n$의 소인수분해가 $p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$이고 $p_i$가 서로 다른 소수라면, 약수의 개수는 다음과 같습니다:

$$d(n) = (e_1 + 1) \cdot (e_2 + 1) \cdots (e_k + 1)$$

이는 다음과 같이 생각해 볼 수 있습니다:

서로 다른 소인수가 하나뿐이어서 $n = p_1^{e_1}$이라면, 약수는 당연히 $e_1 + 1$개($1, p_1, p_1^2, \dots, p_1^{e_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)$입니다.

서로 다른 소인수가 두 개보다 많은 경우에도 비슷한 논증을 할 수 있습니다.

long long numberOfDivisors(long long num) {
    long long total = 1;
    for (int i = 2; (long long)i * i <= num; i++) {
        if (num % i == 0) {
            int e = 0;
            do {
                e++;
                num /= i;
            } while (num % i == 0);
            total *= e + 1;
        }
    }
    if (num > 1) {
        total *= 2;
    }
    return total;
}

약수의 합¶

앞 절과 같은 논증을 사용할 수 있습니다.

서로 다른 소인수 약수가 하나뿐이어서 $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}$$

long long SumOfDivisors(long long num) {
    long long total = 1;

    for (int i = 2; (long long)i * i <= num; i++) {
        if (num % i == 0) {
            int e = 0;
            do {
                e++;
                num /= i;
            } while (num % i == 0);

            long long sum = 0, pow = 1;
            do {
                sum += pow;
                pow *= i;
            } while (e-- > 0);
            total *= sum;
        }
    }
    if (num > 1) {
        total *= (1 + num);
    }
    return total;
}

곱셈적 함수¶

곱셈적 함수란 다음을 만족하는 함수 $f(x)$입니다.

$$f(a \cdot b) = f(a) \cdot f(b)$$

단, $a$와 $b$는 서로소입니다.

$d(n)$과 $\sigma(n)$은 모두 곱셈적 함수입니다.

곱셈적 함수에는 매우 다양하고 흥미로운 성질이 있으며, 이는 정수론 문제에서 매우 유용하게 쓰일 수 있습니다. 예를 들어 두 곱셈적 함수의 디리클레 합성곱도 곱셈적 함수입니다.

약수의 개수 / 약수의 합¶