백준 17427번 약수의 합 2

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

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)를 출력한다.

 

풀이

풀이가 의외로 간단하지만 생각하기 어려웠다.

처음엔 1~100만 까지의 f(x)를 모두 구하고 g(x)를 출력하려 했지만 역시나 시간 초과가 나서 실패했다.

이후에 시도한 방법은 약수의 성질을 이용하는 것이었다.

n이하 k를 약수로 갖는 수의 개수 = n이하의 k의 배수들

이라고 바꿔풀면, n이하 k의 배수들은 n/k가 된다.

ex) 100이하 11의 배수들 -> 11,22,33,44,55,66,77,88,99 총 9개 = 100/11

나머지도 동일하다.

따라서 1부터 n까지의 n/i 값을 모두 더하면, 답이 나온다.

 

소스 코드

#include <iostream>
using namespace std;
 
int main()
{
    int n; scanf("%d", &n);
    long long ans = 0;
    for (int i = 1; i <= n; i++) {
        ans += (n / i) * i;
    }
    printf("%lld", ans);
}

개발환경 : Visual Studio 2019

지적, 조언 언제든지 환영입니다~~