#NOISC2023B. 幂次

幂次

题目描述

小 Ω 在小学数学课上学到了“幂次”的概念:a,bN+\forall a, b \in \N^+,定义 aba^bbbaa 相乘。

她很好奇有多少正整数可以被表示为上述 aba^b 的形式?由于所有正整数 mN+m \in N^+ 总是可以被表示为 m1m^1 的形式,因此她要求上述的表示中,必须有 bkb \geq k,其中 kk 是她事先选取好的一个正整数。

因此她想知道在 11nn 中,有多少正整数 xx 可以被表示为 x=abx = a^b 的形式,其中 a,ba, b 都是正整数,且 bkb \geq k

输入格式

第一行包含两个正整数 n,kn, k,意义如上所述。

输出格式

输出一行包含一个非负整数表示对应的答案。

样例 #1

样例输入 #1

99 1

样例输出 #1

99

样例 #2

样例输入 #2

99 3

样例输出 #2

7

样例 #3

样例输入 #3

99 2

样例输出 #3

12

提示

【样例 2 解释】

以下是全部 77 组符合题意的正整数及对应的一种合法的表示方法。

$1 = 1^3, 8 = 2^3, 16 = 2^4, 27 = 3^3, 32 = 2^5, 64 = 4^3, 81 = 3^4$

注意某些正整数可能有多种合法的表示方法,例如 6464 还可以表示为 64=2664 = 2^6

但根据题意,同一个数的不同的合法表示方法只会被计入一次。

【样例 3 解释】

以下是全部 1212 组符合题意的正整数及对应的一种合法的表示方法。

$1 = 1^2, 4 = 2^2, 8 = 2^3, 9 = 3^2, 16 = 4^2, 25 = 5^2, 27 = 3^3, 32 = 2^5, 36 = 6^2, 49 = 7^2, 64 = 8^2, 81 = 9^2$

【样例 4】

见选手目录下的 power/power4.in 与 power/power4.ans。

【样例 5】

见选手目录下的 power/power5.in 与 power/power5.ans。

【样例 6】

见选手目录下的 power/power6.in 与 power/power6.ans。

【数据范围】

对于所有数据,保证 1n10181 \leq n \leq 10^{18}1k1001 \leq k \leq 100

测试点编号 nn \le kk
1 10210^2 =1=1
2 2\ge 2
3 10410^4 3\ge 3
4 2\ge 2
5 10610^6 3\ge 3
6 2\ge 2
7 10810^8 3\ge 3
8 2\ge 2
9 101010^{10} 3\ge 3
10 2\ge 2
11 101210^{12} 3\ge 3
12 2\ge 2
13 101410^{14} 3\ge 3
14 2\ge 2
15 101610^{16} 3\ge 3
16 2\ge 2
17 101810^{18} 3\ge 3
18 2\ge 2
19
20