[백준 17427번] 약수의 합 2 (C++)

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

17427번: 약수의 합 2

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
const int MAX = 987654321;

int N;
ll result;

int main()
{
    ios_base::sync_with_stdio(0); 
	cin.tie(0);
    
    cin >> N;

    for(int i=1; i<=N; i++)
    {
        result += N/i*i;
    }

    cout << result;

    return 0;
}

 

단순하게 1~N까지 각 약수의 합의 합을 구하면 시간초과가 나는 문제이다.

따라서 따로 규칙을 찾아봐야 한다.

 

해당 문제의 경우 다음과 같은 규칙이 존재했다.

<N = 10>

1 -> 1
2 -> 1, 2
3 -> 1, 3
4 -> 1, 2, 4
5 -> 1, 5
6 -> 1, 2, 3, 6
7 -> 1, 7
8 -> 1, 2, 4, 8
9 -> 1, 3, 9
10 -> 1, 2, 5, 10

1의 갯수 : 10 (10/1)
2의 갯수 : 5 (10/2)
3의 갯수 : 3 (10/3)
4의 갯수 : 2 (10/4)
5의 갯수 : 2 (10/5)
6의 갯수 : 1 (10/6)
7의 갯수 : 1 (10/7)
8의 갯수 : 1 (10/8)
9의 갯수 : 1 (10/9)
10의 갯수 : 1 (10/10

각 수의 갯수 -> N/i

 

따라서 이를 이용하여 누적합을 구할 수 있다.

(현재 수의 갯수 (N/i) * 현재 수i -> (N/i) * i)

 

이때 N의 범위가 100만이고, 누적합을 구해주는 과정에서 int 범위를 초과할 수 있으므로 누적합을 저장할 변수를 long long으로 선언해주어야 한다.