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

문제

두 자연수 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)을 구해보자.

입력

첫째 줄에 테스트 케이스의 개수 T(1 ≤ T ≤ 100,000)가 주어진다. 둘째 줄부터 테스트 케이스가 한 줄에 하나씩 주어지며 자연수 N(1 ≤ N ≤ 1,000,000)이 주어진다.

출력

각각의 테스트 케이스마다, 한 줄에 하나씩 g(N)를 출력한다.

예제 입출력

• 예제 입력 1

5
1
2
10
70
10000

• 예제 출력 1

1
4
87
4065
82256014

Solution

#include <iostream>
#define MAX 100001
#define ll long long
using namespace std;

ll DP[MAX];
ll sum[MAX];
int main(){
    ios::sync_with_stdio(0);
    cin.tie(0);
    fill_n(DP, MAX, 1);
    for(ll i = 2; i < MAX; i++){
        ll j = 1;
        while(i * j < MAX){
            DP[i*j] += i;
            j++;
        }
    }
    for(int i = 1; i < MAX; i++){
        sum[i] += sum[i-1] + DP[i];
    }
    int T; cin >> T;
    while(T--){
        int X; cin >> X;
        cout << sum[X] << '\n';
    }
}

누적 합 문제다. 매번 모든 값들을 구하려고 for문을 돌린다? 지금 현재 문제의 조건을 살펴보면 알겠지만 최대로 들어올 수 있는 숫자는 100000 즉 십만이다. $g(100000)$ 를 계산하면 정말 얼마나 많은 값들을 다시 계산해야할까?

DP 문제라고도 할 수 있지만 엄밀히 따지면 메모이제이션을 활용한 누적합 문제다. 미리 전부 계산해두는 것이다.
2부터 시작해서 십만까지의 숫자들을 기준으로 삼아 $i * j$ 연산을 가능할 때까지 하면서 계속 약수들을 더해주면 되는 문제다.

fill_n(DP, MAX, 1);
for(ll i = 2; i < MAX; i++){
    ll j = 1;
    while(i * j < MAX){
        DP[i*j] += i;
        j++;
    }
}
for(int i = 1; i < MAX; i++){
    sum[i] += sum[i-1] + DP[i];
}

$O(nlgn)$ 의 시간복잡도에 문제를 해결 할 수 있다.while문의 조건에 따라 중간에 많이 끊킬테니까. 이 연산을 초반에 끝내놓으면 앞으로 무슨 값이 들어온들 $O(1)$ 시간에 값을 가져올 수 있다.

누적합이라는 기술에 익숙해질 수 있는 문제. 크게 어렵지 않았다.