자연수 를 자연수 로 나누었을 때 나머지가 이 되면 를 의 약수라고 한다. 예를 들어, 을 로 나누었을 때 나머지가 이므로 는 의 약수가 아니고, 을 으로 나누었을 때 나머지가 이므로 은 의 약수다. 이렇게 의 약수를 모두 나열해보면 , , , 으로 총 개가 된다.
두 자연수 와 가 주어졌을 때, 이상 이하인 모든 수에 대해 각각 약수의 개수를 구해 모두 더한 값을 출력하는 프로그램을 작성하시오.
예를 들어, 입력으로 , 가 주어졌을 때, 의 약수는 과 이고, 의 약수는 , , 이고, 의 약수는 , 이므로 총 약수의 개수는 개이다. 즉, 프로그램이 구해야 하는 답은 이다.
입력 형식
첫 줄에 두 개의 자연수 와 가 공백으로 구분되어 주어진다. ()
출력 형식
첫 줄에 이상 이하인 모든 수에 대해 약수의 개수를 모두 더한 값을 출력한다.
예제 1
입력
1 10
출력
27
예제 2
입력
3 19
출력
57
채점 방식
입력 케이스들은 다음과 같은 종류로 구별되며, 한 종류의 케이스를 다 맞추어야 그 종류에 배정된 점수를 받을 수 있다.
종류 1: 17점
종류 2: 27점
종류 3: 50점
종류 4: 6점
별다른 제약조건 없음.
해설
약수를 주어진 시간안에 빠르게 구하는 문제다. 기본적으로 이상 이하인 수에 대해서 약수의 개수를 모두 더한 값을 알아내는 함수 이 있다고 하자. 이때, 문제에서 요구하는 이상 이하인 모든 수에 대해 약수의 개수를 모두 더한 값은 이 된다.
을 어떤 시간복잡도로 구현하느냐에 따라 점수가 갈리게 되는데, 점을 받기 위해서 시간안에 구현해야 한다. 함수 을 시간복잡도 안에 구현하면 점을 받을 수 있는데, 이는 부터 이하인 모든 수 에 대해 의 합을 구하는 방법이다.