#P2671. Calc

    ID: 1728 传统题 1000ms 128MiB 尝试: 722 已通过: 286 难度: 7 上传者: 标签>CF2300提高+/省选-双射计数整除分块莫比乌斯反演交换求和顺序线性筛倍数枚举

Calc

정수 NN이 주어질 때, 다음 조건을 만족하는 수 쌍 (a,b)(a, b)의 개수를 구하세요:

  1. 1≤a<b≤N1 \leq a < b \leq N
  2. a+ba + b가 a×ba \times b를 나눈다.

입력 형식

한 줄에 정수 NN이 주어집니다.

출력 형식

조건을 만족하는 수 쌍 (a,b)(a, b)의 개수를 출력합니다.

예시

입력:

15

출력:

4

힌트

데이터 범위 및 조건:

  • test1:N≤5×107\text{test1:}N \leq 5 \times 10^7
  • test2:N≤108\text{test2:}N \leq 10^8
  • test3:N≤2×108\text{test3:}N \leq 2 \times 10^8
  • test4:N≤3×108\text{test4:}N \leq 3 \times 10^8
  • test5:N≤5×108\text{test5:}N \leq 5 \times 10^8
  • test6:N≤109\text{test6:}N \leq 10^9
  • test7:N≤109\text{test7:}N \leq 10^9
  • test8:N≤231−1\text{test8:}N \leq 2^{31}-1
  • test9:N≤231−1\text{test9:}N \leq 2^{31}-1
  • test10:N≤231−1\text{test10:}N \leq 2^{31}-1