#G1037. [GESP202403 五级] B-smooth 数

[GESP202403 五级] B-smooth 数

[GESP202403 五级] B-smooth 数

题目描述

小杨同学想寻找一种名为 B-smooth 数的正整数。

如果一个正整数的最大质因子不超过 BB,则该正整数为 B-smooth 数。

小杨同学想知道,对于给定的 nn 和 BB,有多少个不超过 nn 的 B-smooth 数。

输入格式

第一行包含两个正整数 n,Bn, B,含义如题面所示。

输出格式

输出一个非负整数,表示不超过 nn 的 B-smooth 数的数量。

样例 #1

样例输入 #1

10 3

样例输出 #1

7

样例解释

在不超过 10 的正整数中,3-smooth 数有 {1,2,3,4,6,8,9}\{1, 2, 3, 4, 6, 8, 9\},共 7 个。

数据范围

子任务编号 数据点占比 nn BB
1 30 n≤1000n ≤ 1000 1≤B≤10001 ≤ B ≤ 1000
2 n≤106n ≤ 10^6 n≤B≤106\sqrt{n} ≤ B ≤ 10^6
3 40 1≤B≤1061 ≤ B ≤ 10^6
  • 对于全部数据,保证有 1≤n≤1061 ≤ n ≤ 10^6,1≤B≤1061 ≤ B ≤ 10^6。