백준 17427 - 약수의 합 2

문제

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

---

요새 백준으로 푸는 알고리즘에 빠져있다. 근 몇주간 백준만 한 것 같다.
한 달 동안 110문제..? 정도 풀었는데 한동안 받는 외주 + 백준만 풀어댈 것 같다. 하루에 3~4문제는 꾸준히 푼 것 같네.

풀면서 간간히 재밌던 문제들은 이번 한 번 올려보고서 별로 귀찮지 않다면 올려볼 예정.

이번 문제, 처음에는 f(y)를 전부 더해가며 계산했다. (실버 3이니깐 괜찮지 않을까? 싶어서..)

#include <iostream>
using namespace std;

int getM(int n){
    int sum = 0;
    for (int i = 1; i * 2 <= n; ++i) {
        if(n % i == 0){
            sum += i;
        }
    }
    sum += n;
    return sum;
}

int main() {
    int N;
    cin >> N;
    unsigned long long int ans = 0;

    for (int i = 1; i <= N; ++i) {
        ans += getM(i);
    }

    cout << ans << endl;
}

당연히 결과는...

1,000,000을 얕봤다.. 접근 방식 자체가 틀린 것 같아서 처음부터 접근했다.

g(N)를 구하는 f(y)의 규칙이 있지 않을까 싶어서 나열해보았다.

N = 10일 때)
[1][1, 2] [1, 3][1, 2, 4] [1, 5][1, 2, 3, 6] [1, 7][1, 2, 4, 8] [1, 3, 9][1, 2, 5, 10]

잘 살펴보면,
[1이 10번, 2가 5번, 3이 3번, 4가 2번 5가 2번, 6이 1번, ... ,10이 1번] 이렇게 들어가는 규칙을 볼 수 있다.

10 / 2 = 5 니깐 5번..
10 / 3 = 3. 이니 3번..
규칙만 찾으면 코드도 금방 짜여졌다.

#include <iostream>
using namespace std;

int main() {
    int N;
    cin >> N;
    unsigned long long int ans = 0;

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

    cout << ans << endl;
}