QQ의 합

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

요약
곱셈표에서 원소의 합이 정확히 S인 직사각형 영역의 개수를 셉니다. S는 100000 이하입니다.
난이도

어려움10점 중 8점

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

문제

정수 SS가 적힌 카드와 무한한 크기의 구구단 표를 받았다. 표의 모든 원소는 정수이고, 위에서 ii번째 행과 왼쪽에서 jj번째 열에 있는 정수는 Ai,j=i×jA_{i, j} = i \times j이다 (i,j≥1i, j \ge 1). 표는 무한한 크기, 즉 행의 개수와 열의 개수가 무한하다.

당신은 표에서 수들의 합이 SS인 직사각형 영역을 좋아한다. 1≤a≤b1 \leq a \leq b, 1≤c≤d1 \leq c \leq d이고 ∑i=ab∑j=cdAi,j=S\sum_{i=a}^{b} \sum_{j=c}^{d} A_{i,j} = S를 만족하는 정수 순서쌍 (a,b,c,d)(a, b, c, d)의 개수를 세는 것이 과제이다.

입력

입력은 다음과 같은 형식의 단일 테스트 케이스로 이루어진다.

$S$

첫째 줄에 하나의 정수 SS (1≤S≤1051 \leq S \leq 10^5)가 주어지며, 이는 찾아야 하는 직사각형 영역의 합을 나타낸다.

출력

합이 SS인 직사각형 영역의 개수를 한 줄에 출력한다.

예제4

  1. 예제 1

    입력
    25
    
    예상 출력
    10
    
  2. 예제 2

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

    입력
    5
    
    예상 출력
    4
    
  4. 예제 4

    입력
    83160
    
    예상 출력
    5120