[BOJ] 17427번 약수의 합2

링크: https://www.acmicpc.net/problem/17427

---

문제

두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 예를 들어, 2의 약수는 1, 2가 있고, 24의 약수는 1, 2, 3, 4, 6, 8, 12, 24가 있다. 자연수 A의 약수의 합은 A의 모든 약수를 더한 값이고, f(A)로 표현한다. x보다 작거나 같은 모든 자연수 y의 f(y)값을 더한 값은 g(x)로 표현한다.

 

자연수 N이 주어졌을 때, g(N)을 구해보자.

입력

첫째 줄에 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

첫째 줄에 g(N)를 출력한다.

시간제한

0.5 초 (추가 시간 없음)

---

첫번째 시도

이 문제를 처음 접했을 때는 "sqrt(N)까지 반복하면 되지 않을까?"라는 생각 그대로 코드를 작성했다.

 

def get_total_division(x):
    total = 0
    for i in range(1, int(x**(1/2)) + 1):
        if x % i == 0:
            total += i
            if i*i != x:
                total += x//i
    return total

N = int(input())

print(sum([get_total_division(i) for i in range(1, N+1)]))

코드를 제출하기 전에 N의 최댓값인 1,000,000을 넣어보니 TLE가 발생했다.

 

두번째 시도

그래서 더 최적화할 방법이 분명 있다는 확신이 들어 GPT에게 물어봤더니, "약수를 구하지 말고, 배수 관점에서 접근하라"는 답을 들었다.

그러면서 약수를 잘 확인해보라길래, 약수를 나열해 보았다.

def get_divisions(x):
    divisions = []
    for i in range(1, int(x**(1/2)) + 1):
        if x % i == 0:
            divisions.append(i)
            if i*i != x:
                divisions.append(x//i)
    return divisions

N = int(input())

print(*[f"{i}: {get_divisions(i)}" for i in range(1, N+1)], sep="\n")

# N = 10
1: [1]
2: [1, 2]
3: [1, 3]
4: [1, 4, 2]
5: [1, 5]
6: [1, 6, 2, 3]
7: [1, 7]
8: [1, 8, 2, 4]
9: [1, 9, 3]
10: [1, 10, 2, 5]

직접 약수를 나열해보니 흥미로운 패턴이 보였다.

1은 N번 나타나고,

2는 N/2번,

3은 ⌊N/3⌋번 나타난다.

이 사실을 깨닫고, 바로 공식을 이용한 코드를 작성했다.

N = int(input())

result = 0
for i in range(1, N+1):
    result += N // i * i
print(result)

결과적으로 AC를 받았다.

 

하지만 "왜 i가 ⌊N/i⌋번 등장하는가?"가 직관적으로 이해가 되지 않아서, 수식을 통해 원리를 정리해보았다.

 

\(k\)는 자연수이고, \(k\)는 \(n\)과 \(m\)의 배수이다.
$$k = n \times m \quad (n, m, k \in \mathbb{N})$$
\(N\)의 값에 따라 \(k\)는 다음과 같이 정의된다.
$$1 \leq k \leq N$$
따라서,
$$1 \leq n \times m \leq N$$
양변을 \(m\)으로 나누면,
$$\frac{1}{m} \leq n \leq \frac{N}{m}$$
여기서 \(0 < \tfrac{1}{m} \leq 1, \; n \in \mathbb{N}\) 이므로,
$$1 \leq n \leq \left\lfloor \frac{N}{m} \right\rfloor$$
따라서, \(m\)이 정해져 있을 때 \(n\)의 개수는
$$\left\lfloor \frac{N}{m} \right\rfloor$$
개가 된다.