该比赛已结束，您无法在比赛模式下递交该题目。您可以点击“在题库中打开”以普通模式查看和递交本题。

AT_abc300_g [ABC300G] P-smooth number

题目描述

仅以不超过 $k$ 的素数作为素因数的正整数被称为 $k$-smooth 数。
给定整数 $N$ 和不超过 $100$ 的素数 $P$，请你求出不超过 $N$ 的 $P$-smooth 数的个数。

输入格式

输入通过标准输入按以下格式给出。

$N$ $P$

输出格式

请输出答案，结果为一个整数。

样例 1

输入

36 3

输出

14

样例 2

输入

10000000000000000 97

输出

2345134674

说明/提示

限制条件

• $1 \leq N \leq 10^{16}$
• $2 \leq P \leq 100$，且 $P$ 是素数

样例解释 1

不超过 $36$ 的 $3$-smooth 数有 $1,2,3,4,6,8,9,12,16,18,24,27,32,36$ 共 $14$ 个。请注意，$1$ 对于任意素数 $k$ 都是 $k$-smooth 数。

由 ChatGPT 4.1 翻译