P-smooth number

题目描述

如果一个正整数的所有素因子都不超过 $k$，则称其为 $k$-光滑数。
给定一个整数 $N$ 和一个不超过 $100$ 的素数 $P$，求不超过 $N$ 的 $P$-光滑数的个数。

输入格式

输入从标准输入按以下格式给出： $N$ $P$

输出格式

以整数形式输出答案。

36 3

14

10000000000000000 97

2345134674

提示

$N$ 是一个满足 $1 \le N \le 10^{16}$ 的整数。 $P$ 是一个满足 $2 \le P \le 100$ 的素数。不超过 $36$ 的 $3$-光滑数有以下 $14$ 个整数：$1,2,3,4,6,8,9,12,16,18,24,27,32,36$。
注意 $1$ 对于所有素数 $k$ 都是 $k$-光滑数。

标签: AtCoder|abc300G

来源

AtCoder|abc300G