백준 25548번 : 신기한 숫자 2 풀이

1. 문제 링크

https://www.acmicpc.net/problem/25548

 

---

2. 들어가기 전에

25547번 신기한 숫자 문제의 풀이를 정리하던 중, 25548번 문제가 시리즈로 존재한다는 사실을 알게 되었다.

https://www.acmicpc.net/problem/25547

 

---

3. 풀이 방법

(1) 정의

문제에서 이미 $f(A, B)$ 가 정의되어 있고, 이 글에서는 설명을 위해 $F(k)$ 와 $S(k)$ 를 추가로 정의할 것이다.

우선 $F(k) = (k$의 약수의 개수$)$ 로 정의하자.

그리고 $S(k) = F(1) + F(2) + \cdots + F(k) = \sum\limits_{i = 1}^k F(i)$ 로 정의하자.

 

(2) 25547번 풀이에서 밝혀진 사실

25547번 신기한 숫자의 풀이에서, $f(A, B) = \begin{cases} F\left(\cfrac{B}{A}\right) & \operatorname{if} B \mid A \\ 0 & \operatorname{else} \end{cases}$ 가 성립한다는 사실을 알 수 있다.

이에 대한 설명은 지난 번에 올린 25547번 풀이를 확인하면 된다.

(참고로 $B \mid A$ 는 정수 $A$ 를 정수 $B$ 로 나누었을 때 나누어떨어진다는 의미이고, $B \nmid A$ 는 정수 $A$ 를 정수 $B$ 로 나누었을 때 나누어떨어지지 않다는 의미이다.)

 

(3) 식 정리

본격적으로, 문제에서 구해야 할 식을 정리해보자.

$\sum\limits_{i=1}^n \sum\limits_{j=1}^n f(i, j)$

$= \sum\limits_{i=1}^n \sum\limits_{j=1}^n f(j, i)$

$= \sum\limits_{i=1}^n \sum\limits_{j | i} f(j, i)$ ( $\because$ $j\nmid i$ 인 경우에는 어차피 $0$ 이기 때문)

$= \sum\limits_{i=1}^n \sum\limits_{j | i} F\left(\cfrac{i}{j}\right)$ ( $\because$ $j \mid i$ 인 경우, $f(j, i) = F(\cfrac{i}{j})$ 이 성립하기 때문)

 

여기서 $j$ 와 $\cfrac{i}{j}$ 는 둘 다 $i$ 의 약수이므로 다음과 같이 바꿔도 결과는 동일하다.

$\sum\limits_{i=1}^n \sum\limits_{j | i} F\left(\cfrac{i}{j}\right) = \sum\limits_{i=1}^n \sum\limits_{j | i} F\left(j\right) = (식1)$

 

잠시 이해를 돕기 위해 $n = 6$일 때의 예시를 들자.

$i = 1$ 일 때는 $j = 1$ 만 가능하다.

$i = 2$ 일 때는 $j = 1, 2$ 가 가능하다.

$i = 3$ 일 때는 $j = 1, 3$ 이 가능하다.

계속해서 $i = 6$ 까지 반복한 결과를 표로 나타내면 다음과 같다.

i = 1	F(1)
i = 2	F(1)	F(2)
i = 3	F(1)		F(3)
i = 4	F(1)	F(2)		F(4)
i = 5	F(1)				F(5)
i = 6	F(1)	F(2)	F(3)			F(6)

 

이 표를 가로가 아닌 세로 방향으로 본다면 다음이 성립한다는 사실을 알 수 있다.

$6F(1) + 3F(2) + 2F(3) + 1 \cdot F(4) + 1 \cdot F(5) + 1 \cdot F(6)$

$= \left\lfloor \cfrac{6}{1} \right\rfloor F(1) + \left\lfloor \cfrac{6}{2} \right\rfloor F(2) + \left\lfloor \cfrac{6}{3} \right\rfloor F(3) + \left\lfloor \cfrac{6}{4} \right\rfloor F(4) + \left\lfloor \cfrac{6}{5} \right\rfloor F(5) + \left\lfloor \cfrac{6}{6} \right\rfloor \cdot F(6)$

$= \sum\limits_{j = 1}^6 \left\lfloor \cfrac{6}{j} \right\rfloor F(j)$

 

예시에서 확인한 것처럼, $1$ 이상 $n$ 이하의 정수에 대해 그 수의 약수를 구하는 과정에서 $j$가 등장하는 횟수는 $1$ 이상 $n$ 이하의 정수 중 $j$를 약수로 가지는 정수의 개수와 같다.

따라서 아까 전의 식1을 다음과 같이 정리할 수 있다.

$(식1) = \sum\limits_{i=1}^n \sum\limits_{j \mid i} F(j) = \sum\limits_{j=1}^n \left\lfloor \cfrac{n}{j} \right\rfloor F(j) = (식2)$

 

이제 이 값을 어떻게 계산할 것인지가 관건이다.

$1$부터 $n$까지의 모든 $F$ 값을 구해서 이 식을 계산하면 시간 초과가 발생할 것이므로, 더 효율적으로 계산해야 한다.

 

예를 들어 $n=6$인 경우에는 아래의 식을 계산해야 한다.

$6F(1) + 3F(2) + 2F(3) + 1 \cdot F(4) + 1 \cdot F(5) + 1 \cdot F(6)$

 

이 식을 앞에 곱해진 정수에 따라 묶고, 이 글의 도입부에서 정의했던 $S(k) = \sum\limits_{i = 1}^k F(i)$ 를 활용하여 나타내면 아래와 같다.

$6F(1) + 3F(2) + 2F(3) + 1 \cdot \left( F(4) + F(5) + F(6) \right)$

$= 6 \left( S(1) - S(0) \right) + 3 \left( S(2) - S(1) \right) + 2 \left( S(3) - S(2) \right) + 1 \cdot \left( S(6) - S(3) \right)$

 

이렇게 묶은 이유는 $\left\lfloor \cfrac{n}{j} \right\rfloor$ 중 겹치는 수가 많기 때문이다.

실제로 $\left\lfloor \cfrac{n}{j} \right\rfloor$ 중 다른 값의 개수가 $O \left( \sqrt{n} \right)$ 개라는 사실이 알려져 있다고 한다.

$i$ 번째 항에 대해 앞에 곱해진 $\left\lfloor \cfrac{n}{j} \right\rfloor$ 을 $x_i$ , 그리고 그 구간의 시작 값과 끝 값을 각각 $\mathrm{left}_i$ , $\mathrm{right}_i$ 라고 하면 이렇게 정리할 수 있다.

$\sum\limits_i x_i \left( S(\mathrm{right}_i) - S(\mathrm{left}_i - 1) \right)$

 

예를 들어, $n=6$ 의 예시에서는 다음 과정으로 구할 수 있다.

$\mathrm{left}_1 = 1$ $\Rightarrow$ $x_1 = \left\lfloor \cfrac{n}{\mathrm{left}_1} \right\rfloor = \left\lfloor \cfrac{6}{1} \right\rfloor = 6$ $\Rightarrow$ $\mathrm{right}_1 = \left\lfloor \cfrac{n}{x_1} \right\rfloor = \left\lfloor \cfrac{6}{6} \right\rfloor = 1$

$\Rightarrow$ $\mathrm{left}_2 = \mathrm{right}_1 + 1 = 2$ $\Rightarrow$ $x_2 = \left\lfloor \cfrac{n}{\mathrm{left}_2} \right\rfloor = \left\lfloor \cfrac{6}{2} \right\rfloor = 3$ $\Rightarrow$ $\mathrm{right}_2 = \left\lfloor \cfrac{n}{x_2} \right\rfloor = \left\lfloor \cfrac{6}{3} \right\rfloor = 2$

$\Rightarrow$ $\mathrm{left}_3 = \mathrm{right}_2 + 1 = 3$ $\Rightarrow$ $x_3 = \left\lfloor \cfrac{n}{\mathrm{left}_3} \right\rfloor = \left\lfloor \cfrac{6}{3} \right\rfloor = 2$ $\Rightarrow$ $\mathrm{right}_3 = \left\lfloor \cfrac{n}{x_3} \right\rfloor = \left\lfloor \cfrac{6}{2} \right\rfloor = 3$

$\Rightarrow$ $\mathrm{left}_4 = \mathrm{right}_3 + 1 = 4$ $\Rightarrow$ $x_4 = \left\lfloor \cfrac{n}{\mathrm{left}_4} \right\rfloor = \left\lfloor \cfrac{6}{4} \right\rfloor = 1$ $\Rightarrow$ $\mathrm{right}_4 = \left\lfloor \cfrac{n}{x_4} \right\rfloor = \left\lfloor \cfrac{6}{1} \right\rfloor = 6$

$\Rightarrow$ $\mathrm{left}_5 = \mathrm{right}_4 + 1 = 7$ $\Rightarrow$ $\mathrm{left} \gt n$ 이므로 종료

 

이 과정을 코드로 작성하면 다음과 같다. 여기서 $S$ 는 별도의 함수로 따로 분리했다.

long long ans = 0;
int left = 1;

while (left <= n) {
    int x = n / left;
    int right = n / x;
    ans += x * (s(right) - s(left - 1));
    left = right + 1;
}

 

이제 $S(k)$ 를 어떻게 계산할지만 고민하면 된다.

 

(4) S(k) 구하기

$S(k) = \sum\limits_{i = 1}^k F(i)$ 를 구하는 과정도 아까 전의 과정과 매우 유사하다.

예를 들어 $k = 6$ 일 경우 다음의 표로 나타낼 수 있다.

F(1)	+1개
F(2)	+1개	+1개
F(3)	+1개		+1개
F(4)	+1개	+1개		+1개
F(5)	+1개				+1개
F(6)	+1개	+1개	+1개			+1개

 

이 표를 아까처럼 가로가 아닌 세로 방향으로 본다면 다음이 성립한다는 사실을 알 수 있다.

$S(k) = F(1) + F(2) + \cdots + F(k) = \left\lfloor \cfrac{k}{1} \right\rfloor + \left\lfloor \cfrac{k}{2} \right\rfloor + \cdots + \left\lfloor \cfrac{k}{k} \right\rfloor$

즉, $S(k) = \sum\limits_{i = 1}^k \left\lfloor \cfrac{k}{i} \right\rfloor$ 이다.

 

이 식은 아까 전의 식2에서 $F$ 부분을 뺀 것과 같은 식이다.

따라서 식2 이후의 과정을 똑같이 거친다면 결국 다음이 성립함을 알 수 있다.

$\sum\limits_i x_i \left( \mathrm{right}_i - (\mathrm{left}_i - 1) \right)$

 

그리고 이것을 코드로 작성하면 다음과 같다.

long long s(int k) {
    long long res = 0;
    int left = 1;

    while (left <= k) {
        int x = k / left;
        int right = k / x;
        res += x * (right - left + 1);
        left = right + 1;
    }

    return res;
}

 

---

3. 전체 코드 (C++)

• C++ : https://github.com/infikei/algorithm/blob/main/baekjoon_all/25000%2B/boj_25548.cpp