Baekjoon 17425번 약수의 합

문제

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

걸린 시간

-

풀이

C++

#include <bits/stdc++.h>
#define INF 1e9
#define all(c) c.begin(), c.end()
typedef long long ll;
typedef unsigned long long ull;
using namespace std;

string ans = "";
const int N = 1e6;
vector<int> nums(N+1);

map<int, int> factor(int n){
    map<int, int> ret;
    while(n > 1){
        ret[nums[n]]++;
        n = n/nums[n];
    }
    return ret;
}

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

    for(int i = 0; i <= N; i++){
        nums[i] = i;
    }
    nums[0] = nums[1] = 0;
    for(int i = 2; i <= N; i++){
        if(nums[i] == i){
            for(int j = i+i; j <= N; j += i){
                if(nums[j] == j){
                    nums[j] = i;
                }
            }
        }
    }

    vector<ull> ps(N+1, 0);
    for(int i = 1; i <= N; i++){
        auto arr = factor(i);
        ull sum = 1;
        for(auto iter = arr.begin(); iter != arr.end(); iter++){
            ull tmp = 0;
            for(int j = 0; j <= iter->second; j++){
                tmp += round(pow(iter->first, j));
            }
            sum *= tmp;
        }
        ps[i] = sum;
    }

    for(int i = 1; i <= N; i++){
        ps[i] += ps[i-1];
    }

    int tc;
    cin >> tc;
    while(tc--){
        int n;
        cin >> n;
        ans += to_string(ps[n]) + '\n';
    }
    cout << ans;
    return 0;
}

자연수 n 의 최대값이 1e6, 테스트케이스 t 가 최대 1e5 개 주어지므로 매번 g(n) 값을 구하면 O(nt) 는 1e11 로 시간안에 해결할 수 없다.

그래서 모든 수의 f(n) 값을 구해두고 누적합으로 g(n) 값을 구한 뒤 주어지는 n 에 O(1) 로 응답하는 방법을 사용했다.

f(n) 을 얼마나 빨리 구하느냐가 문제인데 O(sqrt(n)) 시간안에 모든 약수를 구하는 방법은 총 O(n^1.5), 1e9 * α 로 통과하지 못한다.

더 빠른 시간안에 약수의 합을 구하는 방법을 찾아보니 O(lgN) 으로 소인수분해를 하고, 소인수를 이용하여 약수의 합을 구하는 방법이 존재했다. O(NlgN) 정도면 확실히 통과할 거라 생각하고 js 로 구현하여 제출했는데 시간초과가 났다. 분명 node.js 의 느린 속도 때문이라고 생각해 c++ 로 재작성해서 제출하니 통과했다. (c++ 이 역시 빠르긴 하다.)

node.js 로 통과한 풀이들은 대부분 dp 풀이이고, 가끔 효율적으로 약수를 직접 구한 풀이가 보인다.

dp 풀이, 에라토스테네스의 체를 이용한 빠른 소인수 분해 방법, 오일러의 체, 또 다른 효율적인 약수 개수 구하는 알고리즘 도 공부하면 좋겠지만 알고리즘 대회가 목적이 아니므로... 여기서 접고 구현 문제나 풀어야겠다.

참고

• 약수의 개수 · 약수의 합을 구하는 방법과 공식을 알기쉽게 알아보자
• [종만북] 빠른 소인수 분해 (에라토스테네스의 체 사용) / 정수론 / Python 파이썬