곱셈적 함수 테이블 만들기

모두 메리 크리스마스!

 

 

 

▣ 정수론 시리즈 ─ 순서대로 읽으시는 걸 추천합니다.

1. 뫼비우스 함수와 디리클레 합성곱

2. Double Counting과 Harmonic Lemma

3. 곱셈적 함수 테이블 만들기 (현재 글)

4. Mertens Trick (xudyh's sieve)

 

  「뫼비우스 함수와 디리클레 합성곱」 게시글에서 여러 곱셈적 함수들의 예시를 소개하였다. 본 글에서는, 곱셈적 함수들의 테이블을 만드는 코드들을 작성해 볼 것이다. 여기서 "함수의 테이블을 만든다"의 의미는 어떤 양의 정수 $N$과 함수 $f(n)$에 대해 $f(1)$, $f(2)$, $\cdots$, $f(N)$의 값을 모두 구한다는 의미이다.

 

양의 약수의 개수 $\tau(n)$

  naive하게 $N$개의 값을 모두 구하면 $\mathcal O(N^{\frac{3}{2}})$의 시간복잡도가 소요된다. 그러나 더블 카운팅을 사용하여, 약수 관점이 아니라 배수 관점으로 본다면 시간복잡도를 줄일 수 있다. 일일이 약수 개수를 세는 것이 아니라 $1$의 배수 함숫값들에 $1$씩 더하고, $2$의 배수 함숫값들에 $1$씩 더하고, …, $N$의 배수 함숫값들에 $1$씩 더해도 $1$부터 $N$까지의 모든 정수의 약수의 개수가 나올 것이다. 이를 코드로 나타내면 다음과 같다.

#include <stdio.h>
#define NMAX 1000003

int tau[NMAX];

int main()
{
	int N, i, j;
	scanf("%d", &N);

	for (i = 1; i <= N; ++i)
		for (j = 1; j*i <= N; ++j) tau[j*i]++;

	for (i = 1; i <= N; ++i) printf("%d ", tau[i]);
	return 0;
}

  에라토스테네스의 체 구현과 비슷한 느낌의 코드다. 위 코드의 시간복잡도를 분석해 보면, $1$ 이상 $N$ 이하의 $i$에 대해 안쪽 for문이 $\lfloor \frac{N}{i} \rfloor$번씩 동작하므로 총 반복문 동작 횟수는

$$\sum _{i=1}^N {\left\lfloor \frac{N}{i} \right\rfloor} \le \sum _{i=1}^N \frac{N}{i} \cong N \ln N$$

가 되어, 코드의 시간복잡도는 $\mathcal O(N \log N)$이 된다. naive한 방법에 비해 상당히 향상되었음을 알 수 있다.

 

양의 약수의 합 $\sigma(n)$

  $\tau(n)$과 유사하게 접근한다. naive하게 일일이 함숫값을 구하면 역시 $\mathcal O(N^{\frac{3}{2}})$이지만, 배수 관점으로 접근해서 풀어보면 $1$의 배수 함숫값들에 $1$씩 더하고, $2$의 배수 함숫값들에 $2$씩 더하고, …, $N$의 배수 함숫값들에 $N$씩 더하는 것으로 볼 수 있다. 이를 코드로 나타내면 다음과 같다.

#include <stdio.h>
#define NMAX 1000003

int sigma[NMAX];

int main()
{
	int N, i, j;
	scanf("%d", &N);

	for (i = 1; i <= N; ++i)
		for (j = 1; j*i <= N; ++j) sigma[j*i] += i;

	for (i = 1; i <= N; ++i) printf("%d ", sigma[i]);
	return 0;
}

  이 코드의 시간복잡도 역시 $\mathcal O(N \log N)$이다.

 

오일러 토션트 함수 $\phi(n)$

  $\phi(n)$의 정의에 입각해서 구한다면, 각 $n$마다 $1$부터 $n$까지의 수를 보며 서로소인지 판별해야 하므로 함숫값 하나 구하는 데에 $\mathcal O(n)$이 걸리게 되어 총 시간복잡도는 $\mathcal O(N^2)$이 된다. 하지만 우리는 $\phi(n)$의 공식을 알고 있으며, 이를 이용해 구한다면 $\mathcal O(N^{\frac{3}{2}})$으로 줄어든다. 그런데 위 함수들처럼 더욱 빨리(구체적으로 $\mathcal O(N \log N)$ 정도의 시간복잡도로) 구할 수는 없을까?

 

  이 글의 〈뫼비우스 반전〉 단락에서 보듯이, $$\sum_{d|n}\phi(d) = n$$가 성립한다. 이를 살짝 변형하면 $$\phi(n) = n - \sum_{d|n,\, d \ne n}\phi(d)$$가 되는데, 몇 개의 작은 $n$에 대해 이 식을 풀어 써 보면 다음과 같다.

$$\begin{aligned}\phi(1) &= 1 \\ \phi(2) &= 2 - \phi(1)  \\ \phi(3) &= 3 - \phi(1) \\ \phi(4) &= 4 - \phi(1) - \phi(2) \\ \phi(5) &= 5 - \phi(1) \\ \phi(6) &= 6 - \phi(1) - \phi(2) - \phi(3) \\ \phi(7) &= 7 - \phi(1) \\ \phi(8) &= 8 - \phi(1) - \phi(2) \,\quad\qquad - \phi(4) \\ \phi(9) &= 9 - \phi(1) \quad\qquad - \phi(3) \end{aligned} \\ \vdots$$

 

  여기서 배수 관점으로 전환한다면, $\phi(n)$의 값을 구할 때 우선 $n$을 더하고, $1$ 이상 $N$ 이하의 모든 정수 $i$에 대해 자기 자신을 제외한 모든 배수들(즉 $2i$, $3i$, … 등)의 함숫값에서 $\phi(i)$가 빠지는 걸 볼 수 있다. 다시 말해 모든 $j \ge 2$에 대해 $\phi(ji)$에서 $\phi(i)$를 빼는 과정을, 모든 $1 \le i \le N$에 대해서 반복하면 $1 \le n \le N$인 모든 $n$에 대해 $\phi(n)$의 값을 구할 수 있다! 이를 코드로 작성하면 다음과 같다.

#include <stdio.h>
#define NMAX 1000003

int phi[NMAX];

int main()
{
	int N, i, j;
	scanf("%d", &N);

	for (i = 1; i <= N; ++i) {
		phi[i] += i;
		for (j = 2; j*i <= N; ++j) phi[j*i] -= phi[i];
	}

	for (i = 1; i <= N; ++i) printf("%d ", phi[i]);
	return 0;
}

  그리고 이 코드 역시, $\mathcal O(N \log N)$의 시간복잡도를 가진다. 모든 $\phi(n)$에 대해 $n$을 더해주는 것을 별개의 반복문으로 처리할 수도 있지만, 좀 더 간결하게 처리한 것에 주목하라.

 

뫼비우스 함수 $\mu(n)$

  뫼비우스 함수도 정의에 따라 구하려면 $n$의 서로 다른 소인수의 개수가 필요하기 때문에, 필연적으로 $\mathcal O(N^{\frac{3}{2}})$의 시간복잡도를 가진다. 그런데 전에 뫼비우스 함수를 소개할 때, 뫼비우스 함수의 성질 중

$$\sum_{d|n}\mu(d) = \begin{cases} 1 & (n = 1) \\ 0 & (n > 1) \end{cases}$$

가 성립한다고 했던 것이 기억나는가? 이 식을 정리하면

$$\mu(n) = \begin{cases} \qquad\quad 1 & (n = 1) \\ - \sum\limits_{d|n,\, d \ne n} \mu(d) & (n > 1) \end{cases}$$

와 같고, 위의 $\phi(n)$ 함수 때와 비슷하게 생각해 보면, $\mu(1) = 1$이고 나머지 값에 대해서는 $j \ge 2$인 모든 $j$에 대해 $\mu(ji)$에서 $\mu(i)$를 빼 주는 걸 모든 $i$에 대해 반복하면 된다. 아래는 이를 바탕으로 작성한 코드다.

#include <stdio.h>
#define NMAX 1000003

int mu[NMAX] = {0, 1}; // 편의상 mu[0] = 0이라 둔다.

int main()
{
	int N, i, j;
	scanf("%d", &N);

	for (i = 1; i <= N; ++i)
		for (j = 2; j*i <= N; ++j) mu[j*i] -= mu[i];

	for (i = 1; i <= N; ++i) printf("%d ", mu[i]);
	return 0;
}

  이 코드도 위의 코드들과 마찬가지로 $\mathcal O(N \log N)$에 동작한다.

 

합성곱 $f \ast g$

  조금 일반화해서, 디리클레 합성곱 $(f \ast g)(n)$의 테이블도 $\mathcal O(N \log N)$에 채울 수 있을까? 물론이다!

 

$$(f \ast g)(n) = \sum_{d|n}f(d)g{\left(\frac{n}{d}\right)} = \sum_{ij=n}f(i)g(j)$$

이므로 $1 \le i \le N$인 모든 $i$에 대해, $(f \ast g)(ji)$에 $f(i)g(j)$를 모든 $j \ge 1$에 대해 더해주는 걸 반복하면 된다. 이를 코드로 나타내면 다음과 같고, 시간복잡도는 $\mathcal O(N \log N)$이다.

#include <stdio.h>
#define NMAX 1000003

int f[NMAX], g[NMAX], fg[NMAX];

int main()
{
	int N, i, j;

	scanf("%d", &N);
	for (i = 1; i <= N; ++i) scanf("%d", &f[i]);
	for (i = 1; i <= N; ++i) scanf("%d", &g[i]);

	for (i = 1; i <= N; ++i)
		for (j = 1; j*i <= N; ++j) fg[j*i] += f[i] * g[j];

	for (i = 1; i <= N; ++i) printf("%d ", fg[i]);
	return 0;
}

 

코드 작성 시 참고할 점

• $N$이 32bit 정수형의 범위를 넘어간다면, 각 코드에서 j*i를 계산할 때 오버플로우를 조심하여야 한다. 오버플로우를 방지하는 방법에 대해서는 내 블로그의 이 글을 참고하라.
• 이렇게 함숫값들을 필요할 때마다 구하는 것이 아니라, 나올 수 있는 모든 값을 미리 전처리해 놓는 것이 더 효율적인 때가 종종 있다. 양쪽의 시간복잡도를 잘 계산해 보고 더 나은 방법을 선택해서 풀자.
• 이 글에서는 $\mathcal O(N \log N)$의 시간복잡도를 가지는 방법에 대해서만 소개하였으나, $\mathcal O(N)$만에 테이블을 만들 수 있는 Linear Sieve라는 게 있다. 이에 대해 궁금한 분들은 해당 블로그에 친절히 잘 설명되어 있으므로 참고하는 걸 추천한다. 개인적으로는, 시간복잡도는 개선되었으나 실제 퍼포먼스에서의 유의미한 차이는 없는 것 같아 사용하지는 않고 있다. 이 부분은 개인의 기호에 따라 고르면 될 것 같다.
• 자연스럽게 곱셈적 함수들의 부분합 테이블 또한 $\mathcal O(N \log N)$만에 채울 수 있게 되었다. "아니, 이전 글에서 $S_{\tau}(N)$과 $S_{\sigma}(N)$을 $\mathcal O(\sqrt N)$에 구하는 방법을 설명해서 의미가 없는 것 아닌가요?"라고 할 수 있지만, 그건 하나의 부분합만을 구하는 것이었고 이건 $N$개의 부분합을 구하는 것이라서 여전히 이 방법이 유효하다. 게다가 $S_{\phi}(N)$과 $S_{\mu}(N)$에 대해서는 아직 나온 바가 없기 때문에, $\phi(n)$과 $\mu(n)$ 한정으로는 부분합 하나를 구할 때도 유용하다!
• 그렇다면 여기서 드는 한 가지 의문. $S_{\phi}(N)$과 $S_{\mu}(N)$을 $\mathcal O(N \log N)$보다 더 빨리 구할 수는 없을까?

 

 

---

 

 

  지금까지 여러 게시글을 넘고 넘은 끝에, 목표했던 정상이 코앞까지 다가왔다. 다음 글이 바로 내가 정수론 시리즈 게시글을 시작한 궁극적인 이유이자 목적이며, 그 글이 위 의문에 대한 답을 제공하게 될 것이다. 부디 다음 글에서도 만날 수 있기를 기대한다!

 

─ To Be Continued…