시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 256 MB 39 12 3 100.000%

문제

재현이는 다음과 같은 소스를 작성했다.

long long mod = 1000000007;
long long all_pair_lcm(int n) {
    long long ans = 0;
    for (int i=1; i<=n-1; i++) {
        for (int j=i+1; j<=n; j++) {
            ans += lcm(i, j);
            ans %= mod;
        }
    }
    return ans;
}

n이 큰 경우에 위의 소스를 그대로 실행하면 시간초과가 난다.

n이 주어졌을 때, all_pair_lcm(n)을 리턴값을 출력하는 프로그램을 작성하시오.

lcm(i, j)는 i와 j의 최소공배수를 구하는 함수이다.

입력

첫째 줄에 n이 주어진다. (1 ≤ n ≤ 106)

출력

첫째 줄에 all_pair_lcm(n)을 리턴값을 출력한다.

예제 입력

2

예제 출력

2

예제 입력 2

5

예제 출력 2

81

예제 입력 3

10

예제 출력 3

1036

예제 입력 4

25

예제 출력 4

38682

힌트

출처

  • 문제를 만든 사람: baekjoon
  • 잘못된 데이터를 찾은 사람: dotorya