C - ABC conjecture 解説 /

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

配点 : 300 点

問題文

正の整数 N が与えられます。

A\leq B\leq C かつ ABC\leq N であるような正の整数の組 (A,B,C) の個数を求めてください。

なお、制約の条件下で答えは 2^{63} 未満であることが保証されます。

制約

  • 1 \leq N \leq 10^{11}
  • N は整数である

入力

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

N

出力

答えを出力せよ。

入力例 1

4

出力例 1

5

条件を満たす組は (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2) の 5 つです。

入力例 2

100

出力例 2

323

入力例 3

100000000000

出力例 3

5745290566750

Score : 300 points

Problem Statement

You are given a positive integer N.

Find the number of triples of positive integers (A, B, C) such that A\leq B\leq C and ABC\leq N.

The Constraints guarantee that the answer is less than 2^{63}.

Constraints

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

Input

Input is given from Standard Input in the following format:

N

Output

Print the answer.

Sample Input 1

4

Sample Output 1

5

There are five such triples: (1,1,1),(1,1,2),(1,1,3),(1,1,4),(1,2,2).

Sample Input 2

100

Sample Output 2

323

Sample Input 3

100000000000

Sample Output 3

5745290566750