#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