백준 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)을 구해보자.

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

---

 

 

 

 

 

 

제한 사항

---

 

 

 

 

 

 

풀이

문제를 요약하면, T개의 x가 주어졌을 때, x보다 작은 수들의 약수의 합을 구해야 한다.

즉, 1부터 x까지 모든 수에 대해 약수를 구하고 그를 모두 더한 값을 구해야 하는 것이다.

 

간단하게는 모두 약수를 구해 더하면 되겠지만 시간 초과가 발생할 것이다.

우선, 약수를 구하는 과정부터 살펴보자.

약수를 구하는 방법은 a로 N을 나누었을 때 나누어 떨어지면 a는 N의 약수이다.

즉, 1부터 N까지 N이 나누어 떨어지는지 확인하면 된다.

이런 방식으로 모든 수의 약수를 구한다면 많은 시간이 필요하다.

하지만, 에라토스테네스의 체를 이용하면 $O(NloglogN)$만에 구할 수 있다.

 

에라토스테네스의 체는 사실 소수를 판별하는 알고리즘이다.

소수를 판별한다는 것은 약수의 개수를 세는 것과 다르지 않기 때문에 사용하기에 적합하다.

 

문제의 요구사항이 모든 약수의 합이기 때문에 에라토스테네스의 체를 통해 약수들의 합을 기록하는 fx를 만든다.

vector<long long> fx(maxNum+1, 0);

//약수 구하기
for (int i = 1; i <= maxNum; i++)
{
    for (int j = i; j <= maxNum; j += i)
    {
        fx[j] += i;
    }
}

 

이후, N보다 작은 모든 수의 fx를 더한 gx는 누적합으로 구할 수 있다.

//누적합
for (int i = 1; i <= maxNum; i++)
{
    gx[i] = gx[i - 1] + fx[i];
}

 

마지막으로 쿼리에 대해 gx를 참조하여 출력하면 된다.

for (int i = 0; i < T; i++)
{
    cout << gx[query[i]] << "\n";
}

---

 

 

 

 

 

전체 코드

#include <bits/stdc++.h>

using namespace std;

int T, N;

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cout << fixed;
    cout.precision(4);

    cin >> T;

    vector<int> query(T);
    int maxNum = 0;
    for (int i = 0; i < T; i++)
    {
        cin >> query[i];
        maxNum = max(maxNum, query[i]);
    }

    vector<long long> fx(maxNum+1, 0);
    vector<long long> gx(maxNum+1, 0);

    //약수 구하기
    for (int i = 1; i <= maxNum; i++)
    {
        for (int j = i; j <= maxNum; j += i)
        {
            fx[j] += i;
        }
    }

    //누적합
    for (int i = 1; i <= maxNum; i++)
    {
        gx[i] = gx[i - 1] + fx[i];
    }

    for (int i = 0; i < T; i++)
    {
        cout << gx[query[i]] << "\n";
    }

    return 0;
}

---