C - 2^a b^2 Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 350 点

問題文

正の整数 X は、次の条件をみたすときかつその時に限り、良い整数と呼ばれます。

  • 正の整数の組 (a,b) を用いて、X=2^a\times b^2 と書ける。

例えば、400 は 400=2^2\times 10^2 と書けるため、良い整数です。

正の整数 N が与えられるので、1 以上 N 以下の良い整数の個数を求めてください。

制約

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

入力

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

N

出力

1 以上 N 以下の良い整数の個数を出力せよ。

入力例 1

20

出力例 1

5

1 以上 20 以下の良い整数は 2,4,8,16,18 の 5 つです。
よって、5 を出力します。

入力例 2

400

出力例 2

24

入力例 3

1234567890

出力例 3

42413

入力が 32bit 整数型に収まるとは限らないことに注意してください。

Score : 350 points

Problem Statement

A positive integer X is called a good integer if and only if it satisfies the following condition:

  • There exists a pair of positive integers (a,b) such that X = 2^a \times b^2.

For example, 400 is a good integer because 400 = 2^2 \times 10^2.

Given a positive integer N, find the number of good integers between 1 and N, inclusive.

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 number of good integers between 1 and N, inclusive.

Sample Input 1

20

Sample Output 1

5

There are five good integers between 1 and 20: 2, 4, 8, 16, and 18.
Thus, print 5.

Sample Input 2

400

Sample Output 2

24

Sample Input 3

1234567890

Sample Output 3

42413

Note that the input might not fit in a 32-bit integer type.