17427 약수의 합 2

시간 제한	메모리 제한	제출	정답	맞힌 사람	정답 비율
0.5 초 (추가 시간 없음)	512 MB	3080	1275	1071	41.351%

문제

두 자연수 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

1

예제 출력 1

1

예제 입력 2

2

예제 출력 2

4

예제 입력 3

10

예제 출력 3

87

예제 입력 4

70

예제 출력 4

4065

예제 입력 5

10000

예제 출력 5

82256014

코드

import java.util.Scanner;

public class P_17427 {
    public static void main(String[] args) {
        long sum = 0;
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        for (int i = 1; i <= n; i++) {
            sum += (long) (n / i) * i;
        }
        System.out.println(sum);
    }
}

코드 설명

10을 예시로 들면 g(10) = f(1) + f(2) + f(3) + ... + f(10)이다.
f(x)는 x의 모든 약수를 더한 값이다.

f(1) = 1
f(2) = 1 + 2
f(3) = 1 + 3
f(4) = 1 + 2 + 4
.
.
.

즉, 1은 10을 1로 나눈 개수만큼 포함이 되므로 10 / 1만큼 더해야하고,
2는 10을 2로 나눈 개수만큼 포함이 되므로 10 / 2 만큼 더해야한다.

그래서 (10 / i) * i만큼 더해야한다.

(n / i) * i

문제에서 제시된 n의 최대 범위는 1,000,000인데 int로 설정할 경우 최대 범위에서의 값이 제대로 구해지지 않기 때문에 long으로 자료형을 설정해야 한다.