103006: [Atcoder]ABC300 G - P-smooth number

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

问题描述

如果一个正整数的所有质因数都不超过$k$，那么我们就称这个数为$k$-平滑数。
给定一个整数$N$和一个不超过$100$的质数$P$，找出不大于$N$的$P$-平滑数的个数。

约束条件

• $N$是一个整数，满足$1 \le N \le 10^{16}$。
• $P$是一个质数，满足$2 \le P \le 100$。

输入

从标准输入按照以下格式给出输入：

$N$ $P$

输出

将答案作为整数输出。

样例输入1

36 3

样例输出1

14

不大于$36$的$3$-平滑数有以下$14$个整数：$1,2,3,4,6,8,9,12,16,18,24,27,32,36$。
注意，对于所有的质数$k$，$1$都是一个$k$-平滑数。

样例输入2

10000000000000000 97

样例输出2

2345134674