当前没有测试数据。

G - P-smooth number

分数 ： $600$ 分

问题描述

一个正整数被称为 $k$ 光滑数，如果它的所有质因数都不超过 $k$。
给定一个整数 $N$ 和一个不超过 $100$ 的质数 $P$，找出不超过 $N$ 的 $P$ 光滑数的数量。

限制条件

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

输入

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

$N$ $P$

输出

将答案以整数形式输出。

36 3

14

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

10000000000000000 97

2345134674