E - Product-Bounded Arithmetic Sequences 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 450 点

問題文

以下の条件を全て満たす正整数列 A=(A_1,\dots,A_{|A|}) を良い数列と定めます。

  • |A|\geq 3
  • A は等差数列である。即ち、全ての 1 \leq i \leq |A|-1 について A_{i+1}-A_{i}=A_2-A_1
  • A_2-A_1 > 0

良い数列のうち、要素の総積が N 以下であるものの個数を求めてください。

なお、制約の条件下で答えが 10^{18} 以下となることが証明されます。

制約

  • 1 \leq N \leq 10^{18}
  • N は整数

入力

入力は以下の形式で標準入力から与えられる。

N

出力

答えを出力せよ。

入力例 1

120

出力例 1

18

総積が 24 以下の良い数列は (1,2,3),(1,2,3,4),(1,3,5),(2,3,4) の 4 個です。

入力例 2

1000000000000000000

出力例 2

1051148114007

Score : 450 points

Problem Statement

A sequence of positive integers A=(A_1,\dots,A_{|A|}) is called a good sequence if it satisfies all of the following conditions.

  • |A|\geq 3
  • A is an arithmetic progression; that is, A_{i+1}-A_{i}=A_2-A_1 for all 1 \leq i \leq |A|-1.
  • A_2-A_1 > 0

Find the number of good sequences such that the product of all elements is at most N.

It can be proved that the answer is at most 10^{18} under the constraints.

Constraints

  • 1 \leq N \leq 10^{18}
  • N is an integer.

Input

The input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

120

Sample Output 1

18

There are 4 good sequences whose product is at most 24: (1,2,3),(1,2,3,4),(1,3,5),(2,3,4).

Sample Input 2

1000000000000000000

Sample Output 2

1051148114007