G - P-smooth number Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

配点 : 600

問題文

k 以下の素数のみを素因数に持つ正整数を k-smooth number と呼びます。
整数 N および 100 以下の素数 P が与えられるので、 N 以下の P-smooth number の個数を求めてください。

制約

  • N1 \le N \le 10^{16} を満たす整数
  • P2 \le P \le 100 を満たす素数

入力

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

N P

出力

答えを整数として出力せよ。


入力例 1

36 3

出力例 1

14

36 以下の 3-smooth number は 1,2,3,4,6,8,9,12,16,18,24,27,32,3614 個です。
1 は任意の素数 k に対して k-smooth number であることに注意してください。


入力例 2

10000000000000000 97

出力例 2

2345134674

Score : 600 points

Problem Statement

A positive integer is called a k-smooth number if none of its prime factors exceeds k.
Given an integer N and a prime P not exceeding 100, find the number of P-smooth numbers not exceeding N.

Constraints

  • N is an integer such that 1 \le N \le 10^{16}.
  • P is a prime such that 2 \le P \le 100.

Input

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

N P

Output

Print the answer as an integer.


Sample Input 1

36 3

Sample Output 1

14

The 3-smooth numbers not exceeding 36 are the following 14 integers: 1,2,3,4,6,8,9,12,16,18,24,27,32,36.
Note that 1 is a k-smooth number for all primes k.


Sample Input 2

10000000000000000 97

Sample Output 2

2345134674