티스토리 뷰

정보과학/알고리즘

약수의 개수

leejseo 2019. 8. 16. 21:55

PS 하면서 약수의 개수와 관련된 문제를 종종 볼 수 있다. 그래서 글을 작성중이었는데, 마침 NYPC에 이 글의 내용 중 일부를 그대로 쓰면 되는 문제가 나왔다고 한다. 그래서 글을 날렸고, NYPC 예선이 끝난 이제야 업로드한다. 글을 날렸던 만큼 다듬어지지 않았을 수 있다. 나중에 수정할 예정이다.

1. 약수의 개수 구하기

양의 정수 $N$이 주어지고, $N$의 약수의 개수를 구한다고 해보자. $O(\sqrt{N})$ 알고리즘 부터 소개하겠다.

이 알고리즘은 간단하다. $N = xy$로 나타내어 진다고 할 때, $x$와 $y$중 하나는 $\sqrt{N}$ 이하이고, 다른 하나는 $\sqrt{N}$ 이상이다. 따라서, $\sqrt{N}$ 이하의 수들만 봐도 약수의 개수를 구할 수 있다.

C++ 구현은 다음과 같다.

 

void find_prime(int N, vector<int> &res){
    for (int x = 1; x*x <= N; x++){
        int y = N/x;
        if (x*y != N) continue;
        res.push_back(x);
        if (y != x) res.push_back(y);
    }
}

 

하지만, $N \le 10^{18}$과 같이 $N$이 커진다면 이 알고리즘은 충분히 빠르지 못할 것이다. 이런 경우에도 사용할 수 있는 $O(N^{\frac13+\epsilon})$ 알고리즘을 소개한다.

 

본론에 앞서, 알고리즘의 정당성의 근거가 되는 내용을 먼저 설명하도록 하겠다. $f(n)$을 $n$의 약수의 개수라고 하자. 그러면, $f(n)$은 곱셈함수(multiplicative function)임이 명백하다. 다시 말해, $\gcd(n, m) = 1$일 때, $f(nm)  = f(n)f(m)$이다. 이제, $n$을 소수의 거듭제곱 $p_1^{a_1} p_2^{a_2} \cdots p_k ^{a_k}$로 쓸 수 있다고 할 때, $f(n) = f(p_1^{a_1}) f(p_2^{a_2}) \cdots f(p_k^{a_k})$ 임을 알 수 있다.

 

본론에 들어가자면, 먼저, 전처리를 통해 $N^{\frac13}$ 이하의 소수를 모두 구해놓는다. 이는 에라토스테네스의 체를 통해 $O(N^{\frac13 + \epsilon})$ 시간에 가능하다. 이제, $N$을 두 개의 수 $X, Y$의 곱으로 나타내는데, 이 때, $X$는 $N^{\frac13}$ 이하의 소인수로만 이루어져 있고, $Y$는 $N^{\frac13}$ 이상의 소인수로 이루어져 있다.

 

이 두 수 $X$와 $Y$를 구하는 것은 명백하게 $O(N^{\frac13})$ 시간에 할 수 있다. 이제, $X$를 소인수분해 하면 $f(X)$를 계산할 수 있다. $f(Y)$의 경우 몇 개의 경우를 나누어서 따져보면 되는데, $Y$는 (1) 소수이거나, (2) 두 소수의 곱이거나(3) 소수의 제곱 이 세 가지 경우중 하나에 속한다. 어느 경우에 속하는지 판별하는데 있어서는 밀러-라빈 소수판정법을 사용하면 되는데, 밀러-라빈 소수판정법 또한 빠르게 작동하게 된다.

 

그리고, $f(N) = f(X)f(Y)$ 이므로, 총 $O(N^{\frac13 + \epsilon})$ 시간에 $N$의 약수의 개수를 구할 수 있게 된다.

구현된 코드는 첨부하지 않는다.

2. 약수의 개수의 합

NYPC 2019에 이 내용이 그대로 출제되었다는 것을 듣고, 글을 업로드 하려다가 하지 않았다. 이제 예선 대회가 끝났으니 업로드 한다. 사실 이것은 PS라기 보단 수학에 더 가깝다. 실제로 예전에도 수학공부하다가 해봤었고.

 

$1$부터 $x$까지 자연수들의 약수의 개수의 합을 $F(x)$라 하면, 다음이 성립함은 명백하다:

$$ F(x) = \lfloor \frac{x}{1} \rfloor + \lfloor \frac{x}{2} \rfloor + \cdots + \lfloor \frac{x}{x} \rfloor.$$

이 식을 그대로 이용하면 $F(n)$을 $O(n)$ 시간에 구할 수 있다. 하지만 이는 너무 느리다. $F(n)$을 $O(\sqrt{n})$ 시간에 구하는 방법을 설명하고자 한다.

 

$f_n(x) = \lfloor \frac{x}{n} \rfloor$이라 하자. 그러면, $F(x)  = \sum_{n=1}^{x} f_n(x)$가 된다.

우리는 $n > \sqrt{x}$인 경우에 주목할 것이다. $n > \sqrt{x}$인 $n$에 대해 $f_n(x)$들의 합은 $mn \le x$이고, $n > \sqrt{x}$인 자연수의 순서쌍 $(m, n)$의 수와 같다. 이는, 다음을 만족하는 $(m, n)$의 수와도 같다:

$$ \sqrt{x} < n \le \frac{x}{m}.$$

이 때, $m \le \sqrt{x}$ 여야 함은 명백하다. 이제, 반대로 $m$을 고정하고, 이를 만족하는 $n$의 개수를 구해보자. $n$은 $\sqrt{x}$ 초과 $\frac{x}{m}$ 이하인 자연수의 갯수이므로, 이는 $\lfloor \frac{x}{m} \rfloor - \lfloor \sqrt{x} \rfloor$이 된다. 이제, $1 \le m \le \sqrt{x}$에 대해 이 값들을 합해주면, $$\begin{align*} \sum_{n=\lfloor \sqrt{x} \rfloor + 1}^{x} f_n(x) &= \sum_{m=1}^{\lfloor \sqrt{x} \rfloor} \left( \lfloor \frac{x}{m} \rfloor - \lfloor \sqrt{x} \rfloor \right) \\ &= \sum_{m=1}^{\lfloor \sqrt{x} \rfloor} \lfloor \frac{x}{m} \rfloor - \lfloor \sqrt{x} \rfloor^2 \\ &= \sum_{m=1}^{\lfloor \sqrt{x} \rfloor} f_m(x) - \lfloor \sqrt{x} \rfloor^2 \end{align*}$$

이 된다.

 

이제, 다시 돌아와서 $F(x)$를 계산해보자.

$$\begin{align*} F(x) &= \sum_{n=1}^{x} f_n(x) \\ &= \sum_{n=1}^{\lfloor \sqrt{x} \rfloor} f_n(x) + \sum_{n=\lfloor \sqrt{x} \rfloor + 1}^{x} f_n(x) \\ &=\sum_{n=1}^{\lfloor \sqrt{x} \rfloor} f_n(x) +\sum_{m=1}^{\lfloor \sqrt{x} \rfloor} f_m(x) - \lfloor \sqrt{x} \rfloor^2 \\ &= 2  \sum_{n=1}^{\lfloor \sqrt{x} \rfloor}  f_n(x) -\lfloor \sqrt{x} \rfloor^2 \\ &= 2\sum_{m=1}^{\lfloor \sqrt{x} \rfloor} \lfloor \frac{x}{m} \rfloor - \lfloor \sqrt{x} \rfloor^2 \end{align*}$$

 

이제, 이 $F(x)$를 그대로 계산해주자. 그러면 앞서 언급했듯이 제곱근 정도의 시간복잡도에 $F$를 계산할 수 있다.

댓글
댓글쓰기 폼