[BOJ-17427][C++] 약수의 합 2

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	512 MB	6734	2683	2292	40.147%

 

문제

두 자연수 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)를 출력한다.

 

예제 입력 1

1

 

예제 출력 1

1

 

예제 입력 2

2

 

예제 출력 2

4

 

예제 입력 3

10

 

예제 출력 3

87

 

예제 입력 4 

70

 

예제 출력 4

4065

 

예제 입력 5

10000

 

예제 출력 5 

82256014

 

알고리즘 분류

• 수학
• 정수론

 

문제 출처

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

17427번: 약수의 합 2

 

---

 

문제 해결 방법

• 제한 시간 0.5초의 문제로, 최대한 빠른 알고리즘을 작성해야 하는 것이 문제 해결의 핵심이었다.
• 시간 제한만 없었더라면 다음과 같이 DP를 이용하여 알고리즘을 작성해볼 수도 있었다. ($O(N^{2})$)

using ULL = unsigned long long;
ULL dp[1000001];

ULL Solution(int n) {
    ULL sum;

    dp[1] = 1;
    for (int i = 2; i <= n; i++) {
        sum = 0;
        for (int j = 1; j <= i; j++) {
            if (i % j == 0) {
                sum += j;
            }
        }
        dp[i] = dp[i - 1] + sum;    // 누적합
    }

    return dp[n];
}

 

• $O(N^{2})$으로 문제를 푸는 방식이 아닌, 새로운 방식으로 문제를 해결해야 한다.
• @N = 10@일 때, @1@부터 @10(N)@까지의 약수를 구하면 다음과 같다.

f(N)	약수	약수의 개수	합
f(1)	{ 1 }	1	1
f(2)	{ 1, 2 }	2	3
f(3)	{ 1, 3 }	2	4
f(4)	{ 1, 2, 4 }	3	7
f(5)	{ 1, 5 }	2	6
f(6)	{ 1, 2, 3, 6 }	4	12
f(7)	{ 1, 7 }	2	8
f(8)	{ 1, 8 }	2	9
f(9)	{ 1, 3, 9 }	3	13
f(10)	{ 1, 2, 5, 10 }	4	18

• @f(1)@부터 @f(10)@까지의 각각의 약수의 개수들과 그 규칙을 보면 다음과 같다. 

약수(i)	개수(num)	규칙(N / i = num)
1	10개	10 / 1 = 10
2	5개	10 / 2 = 5
3	3개	10 / 3 = 3
4	2개	10 / 4 = 2
5	2개	10 / 5 = 2
6	1개	10 / 6 = 1
7	1개	10 / 7 = 1
8	1개	10 / 8 = 1
9	1개	10 / 9 = 1
10	1개	10 / 10 = 1

• @g(10) = f(1) + f(2) + f(3) + f(4) + f(5) + f(6) + f(7) + f(8) + f(9) + f(10)@ 이다.
• 즉, @g(10) = (1 × 10) + (2 × 5) + (3 × 3) + (4 × 2) + (5 × 2) + (6 × 1) + (7 × 1) + (8 × 1) + (9 × 1) + (10 × 1)@ 이므로, 다음과 같은 알고리즘을 작성할 수 있다.

long long sum = 0;
long long Solution(int n) {
    for (int i = 1; i <= n; i++) {
        sum += i * (n / i);
    }
    return sum;
}

 

코드

#include <iostream>
using namespace std;

int N;
long long sum;

void Input() {
    cin >> N;
}

long long Solution(int n) {
    for (int i = 1; i <= n; i++) {
        sum += i * (n / i);
    }
    return sum;
}

void Output() {
    cout << Solution(N) << '\n';
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    cout.tie(NULL);

    Input();
    Output();

    return 0;
}

 

채점 결과

 

참고

• 실버II