직사각형 2

시간 제한2초메모리 제한512 MB

요약
양의 정수 순서쌍 (a, b) 중 a <= b이고 a*b <= n인 쌍의 개수를 센다.
난이도

보통10점 중 4점

유형
수학, 정수론, 완전 탐색
정답자
아직 제출이 없습니다

문제

바이트맨은 한 변의 길이가 11인 정사각형(단위 정사각형)을 nn개 가지고 있다. 이 정사각형들을 사용해서 서로 다른 직사각형을 몇 종류나 만들 수 있을까?

두 직사각형은 한쪽을 아무리 회전하거나 평행이동해도 다른 쪽과 완전히 포갤 수 없을 때 서로 다르다고 본다. 직사각형을 만들 때 바이트맨은 정사각형을 변형할 수 없고, 어떤 정사각형을 다른 정사각형 위에 겹쳐 쌓을 수도 없다.

가로와 세로가 각각 양의 정수 aa, bb인 직사각형은 정확히 a⋅ba \cdot b개의 단위 정사각형으로 이루어지므로, a⋅b≤na \cdot b \le n일 때에만 만들 수 있다. 또한 어떤 직사각형과 그것을 90∘90^\circ 돌린 것(a×ba \times b와 b×ab \times a)은 같은 직사각형으로 센다.

입력

표준 입력의 처음이자 유일한 줄에 정수 nn이 하나 주어진다 (1≤n≤1 000 000 0001 \le n \le 1\,000\,000\,000).

출력

바이트맨이 가진 정사각형들로 만들 수 있는 서로 다른 직사각형의 개수를 정수 하나로 출력한다.

힌트

예제3

  1. 예제 1

    입력
    6
    
    예상 출력
    8
    
  2. 예제 2

    입력
    1
    
    예상 출력
    1
    
  3. 예제 3

    입력
    4
    
    예상 출력
    5