/ 
Time Limit: 4 sec / Memory Limit: 1024 MB
配点 : 600 点
問題文
k 以下の素数のみを素因数に持つ正整数を k-smooth number と呼びます。
整数 N および 100 以下の素数 P が与えられるので、 N 以下の P-smooth number の個数を求めてください。
制約
- N は 1 \le N \le 10^{16} を満たす整数
- P は 2 \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,36 の 14 個です。
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