题目描述
Problem Description
Little Ω learned about the concept of "power" in her elementary math class: for all \( a, b \in \mathbb{N}^+ \), \( a^b \) is defined as \( b \) multiplied by \( a \).
She is curious about how many positive integers can be expressed in the form of \( a^b \)? Since every positive integer \( m \in \mathbb{N}^+ \) can always be expressed as \( m^1 \), she requires that in the above representation, \( b \geq k \), where \( k \) is a positive integer she has chosen in advance.
Therefore, she wants to know how many positive integers \( x \) between 1 and \( n \) can be expressed in the form \( x = a^b \), where \( a \) and \( b \) are positive integers and \( b \geq k \)?
Input Format
The first line contains two positive integers \( n \) and \( k \), as described above.
Output Format
Output a single line containing a non-negative integer representing the corresponding answer.
Sample Input and Output
Sample Input #1
99 1
Sample Output #1
99
Sample Input #2
99 3
Sample Output #2
7
Sample Input #3
99 2
Sample Output #3
12
Notes
[Sample 2 Explanation]
The following are all 7 positive integers that meet the criteria and a corresponding valid representation method.
\( 1 = 1^3, 8 = 2^3, 16 = 2^4, 27 = 3^3, 32 = 2^5, 64 = 4^3, 81 = 3^4 \)
Note that some positive integers may have multiple valid representation methods, such as \( 64 \) which can also be represented as \( 64 = 2^6 \).
However, according to the problem statement, different valid representations of the same number will only be counted once.
[Sample 3 Explanation]
The following are all 12 positive integers that meet the criteria and a corresponding valid representation method.
\( 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 \)
[Sample 4]
See the power/power4.in and power/power4.ans files in the contestant directory.
[Sample 5]
See the power/power5.in and power/power5.ans files in the contestant directory.
[Sample 6]
See the power/power6.in and power/power6.ans files in the contestant directory.
[Data Range]
For all data, it is guaranteed that \( 1 \leq n \leq 10^{18} \) and \( 1 \leq k \leq 100 \).
| Test Point Number | \( n \leq \) | \( k \) |
|---|---|---|
| 1 | \( 10^2 \) | \( =1 \) |
| 2 | \( 10^2 \) | \( \geq 2 \) |
| 3 | \( 10^4 \) | \( \geq 3 \) |
| 4 | \( 10^4 \) | \( \geq 2 \) |
| 5 | \( 10^6 \) | \( \geq 3 \) |
| 6 | \( 10^6 \) | \( \geq 2 \) |
| 7 | \( 10^8 \) | \( \geq 3 \) |
| 8 | \( 10^8 \) | \( \geq 2 \) |
| 9 | \( 10^{10} \) | \( \geq 3 \) |
| 10 | \( 10^{10} \) | \( \geq 2 \) |
| 11 | \( 10^{12} \) | \( \geq 3 \) |
| 12 | \( 10^{12} \) | \( \geq 2 \) |
| 13 | \( 10^{14} \) | \( \geq 3 \) |
| 14 | \( 10^{14} \) | \( \geq 2 \) |
| 15 | \( 10^{16} \) | \( \geq 3 \) |
| 16 | \( 10^{16} \) | \( \geq 2 \) |
| 17 | \( 10^{18} \) | \( \geq 3 \) |
| 18 | \( 10^{18} \) | \( \geq 2 \) |
| 19 | \( 10^{18} \) | \( \geq 2 \) |
| 20 | \( 10^{18} \) | \( \geq 2 \) |
输入格式
见题面 Input 部分
输出格式
见题面 Output 部分