[2247] 실질적 약수

문제 링크 : https://www.acmicpc.net/problem/2247

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$)을 $1000000$으로 나눈 나머지를 출력한다.

제한

시간 제한	메모리 제한
2sec	128MB

• $1 \leq n \leq 200000000$ ($2 \times 10^8$)

---

풀이

SOD 함수를 정의하는 것은 어려울 것 같다. 각 정수마다 모든 약수의 합을 구하고, 거기서 1과 자기 자신을 제외하여 계산할 것인데, 각 수마다 약수의 개수가 소인수 분해한 결과 $a^p \times b^q \times c^r \cdots$일 때 $(p+1) \times (q+1) \times (r+1) \cdots$ 개수만큼 존재한다. 2억까지 입력이 가능한 이 문제에서 이 방법으로 2초 안에 계산할 수는 없을 것 같다.

그래서, SOD 함수를 계획하지 말고 바로 CSOD 함수를 계획해보는 방향으로 생각해보자. 2를 약수로 가지는 수들은 어떤 것들이 있을까? 2, 4, 6, 8… 2의 배수들이 2를 약수로 가진다는 것은 당연히 알 수 있다. 그럼 그 수들의 개수는? 수들은 1부터 $n$까지 존재하므로, 2의 배수는 그 중에서 $\lfloor \frac{n}{2} \rfloor$개 존재함을 계산할 수 있다. 그들 중 SOD(2)에서는 2가 포함되면 안되므로, CSOD($n$)에서 2의 개수는 $\lfloor \frac{n}{2} - 1 \rfloor$개라고 계산할 수 있다. 이것을 일반화하면 아래 식과 같다.

\[\text{CSOD}(n) = \sum_{i=1}^{n - 1} (\lfloor \frac{n}{i} - 1 \rfloor \times i)\]

이것을 그대로 코드에 녹여서 계산하면 답을 구할 수 있다. 문제에서 나머지를 구하라고 하였으므로 그때그때마다 나머지 연산을 해주도록 하자.

• 참고 알고리즘 :

코드

사용 언어 : C

최종 수정일 : 2023 / 2 / 14

#include <stdio.h>

#define MOD (int)(1e6)

int main() {
    int retval = 0;
    int n;
    scanf("%d", &n);

    for (int i = 2; i < n; ++i) {
        retval += (((n / i) - 1) * i);
        retval %= MOD;
    }

    printf("%d", retval);
    return 0;
}