실질적 약수
시간 제한2초메모리 제한128 MB
n이 최대 2억일 때 1부터 n까지의 진약수 합을 누적한 값을 100만으로 나눈 나머지를 효율적으로 구하는 문제입니다.
문제
자연수 A와 C에 대해, 어떤 자연수 B가 존재하여 A = B × C라면 C를 A의 약수라고 한다. 모든 자연수 N은 항상 1과 N을 약수로 가진다.
이 문제에서는 N의 약수 중 1과 N을 제외한 약수를 실질적 약수라고 부른다. 예를 들어 6의 실질적 약수는 2와 3이고, 13의 실질적 약수는 없다.
SOD(n)을 자연수 n의 모든 실질적 약수의 합으로 정의하자. 따라서 SOD(6) = 5이고 SOD(13) = 0이다. 또한 CSOD(n)을 SOD(1) + SOD(2) + ... + SOD(n)으로 정의한다.
정수 n이 주어졌을 때 CSOD(n)을 구하라.
입력
첫째 줄에 정수 n이 주어진다.
출력
첫째 줄에 CSOD(n)을 1,000,000으로 나눈 나머지를 출력한다.
제한
- 1 ≤ n ≤ 200,000,000