[BOJ 2247] 실질적 약수
- 문제풀이
문제
두 자연수 A와 B가 있을 때, A = BC를 만족하는 자연수 C를 A의 약수라고 한다. 모든 자연수 N은 1과 자기 자신(N)을 약수로 갖게 된다.
실질적 약수(actual divisor)라는 것이 있다. 자연수 N의 약수들 중에서 1과 자기 자신(N)을 제외한 약수를 실질적 약수라고 한다. 따라서 6의 실질적 약수는 2, 3이며, 13의 실질적 약수는 없다.
SOD(Sum Of Divisor)라는 함수를 정의하자. SOD(n)은 정수 n의 모든 실질적 약수의 합을 가리킨다. 따라서 SOD(6) = 5이며, SOD(13) = 0이다. 한편, CSOD(Cumulative SOD)라는 함수도 정의해 볼 수 있다. CSOD(n)은 SOD(1) + SOD(2) + … + SOD(n)이라고 하자.
CSOD(n)을 구하는 프로그램을 작성하시오.
입력
첫째 줄에 정수 n이 주어진다.
출력
첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다.
제한
| 시간 제한 | 메모리 제한 |
|---|---|
| 2sec | 128MB |
- 1 ≤ n ≤ 200,000,000
풀이
자연수 $n$의 모든 실질적 약수(1과 자기 자신을 제외한 약수)의 합을 $SOD(n)$이라 할 때, $1$부터 $n$까지의 모든 $SOD$ 값의 합인 $CSOD(n)$을 구하는 문제다.
가장 먼저 떠오르는 방법은 $1$부터 $n$까지 반복문을 돌며 각 숫자의 약수를 직접 찾는 것이다. 하지만 이 문제에서 $n$은 최대 $200\,000\,000$에 달한다. 각 수마다 약수를 구하는 방식은 $O(n\sqrt{n})$의 시간 복잡도를 가지므로, 제한 시간 $2$초 내에 해결하는 것은 불가능하다.
따라서 관점을 바꾸어 “어떤 정수 $i$가 $1$부터 $n$까지의 숫자들 중 몇 번이나 실질적 약수로 포함되는가?”를 계산해야 한다.
임의의 정수 $i$에 대하여, $n$ 이하의 숫자 중 $i$를 약수로 가지는 숫자는 $i$의 배수들이다. 그 개수는 다음과 같다.
\[\lfloor n / i \rfloor\]하지만 문제에서 정의한 ‘실질적 약수’는 $1$과 자기 자신을 제외한다. $i$의 배수들 중 $i \times 1 = i$인 경우, $i$는 자기 자신의 약수가 되므로 실질적 약수의 조건에서 제외되어야 한다. (또한 $i=1$인 경우는 고려하지 않는다.) 따라서 $i$가 실질적 약수로 등장하는 실제 횟수는 다음과 같다.
\[\lfloor n / i \rfloor - 1\]결과적으로 우리가 구하고자 하는 $CSOD(n)$의 총합은 각 $i$가 실질적 약수로 기여하는 값들을 모두 더한 것과 같다.
\[CSOD(n) = \sum_{i=2}^{n} i \times (\lfloor n / i \rfloor - 1)\]이 공식은 $i$에 대한 단일 반복문으로 구현할 수 있으므로 $O(n)$의 시간 복잡도를 가진다. $2 \times 10^8$ 정도의 연산은 C언어에서 충분히 제한 시간 내에 수행 가능하다. 매 덧셈마다 $1\,000\,000$으로 나눈 나머지를 취하여 오버플로우를 방지하는 것을 잊지 말자.
소스코드
Github Link : Source Code
참고 알고리즘 :