P9118 [Spring Test 2023] Powers

In elementary math class, Little $\Omega$ learned the concept of “powers”: $\forall a, b \in \N^+$, define $a^b$ as the product of $b$ copies of $a$ multiplied together. She is curious about how many positive integers can be written in the form $a^b$ above. Since every positive integer $m \in \N^+$ can always be written as $m^1$, she requires that in such a representation, we must have $b \geq k$, where $k$ is a positive integer chosen in advance. Therefore, she wants to know: among the integers from $1$ to $n$, how many positive integers $x$ can be written as $x = a^b$, where $a$ and $b$ are both positive integers and $b \geq k$?

The first line contains two positive integers $n, k$, with the meanings described above.

Output one line containing one non-negative integer representing the corresponding answer.

**[Explanation for Sample 2]** The following are all $7$ positive integers that satisfy the requirement, along with one valid representation for each. $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 representations. For example, $64$ can also be written as $64 = 2^6$. However, according to the statement, different valid representations of the same number are counted only once. **[Explanation for Sample 3]** The following are all $12$ positive integers that satisfy the requirement, along with one valid representation for each. $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 power/power4.in and power/power4.ans in the contestant directory. **[Sample 5]** See power/power5.in and power/power5.ans in the contestant directory. **[Sample 6]** See power/power6.in and power/power6.ans in the contestant directory. **[Constraints]** For all testdata, it is guaranteed that $1 \leq n \leq 10^{18}$ and $1 \leq k \leq 100$. |Test Point ID|$n \le$|$k$| |:-:|:-:|:-:| |1|$10^2$|$=1$| |2|$10^2$|$\ge 2$| |3|$10^4$|$\ge 3$| |4|$10^4$|$\ge 2$| |5|$10^6$|$\ge 3$| |6|$10^6$|$\ge 2$| |7|$10^8$|$\ge 3$| |8|$10^8$|$\ge 2$| |9|$10^{10}$|$\ge 3$| |10|$10^{10}$|$\ge 2$| |11|$10^{12}$|$\ge 3$| |12|$10^{12}$|$\ge 2$| |13|$10^{14}$|$\ge 3$| |14|$10^{14}$|$\ge 2$| |15|$10^{16}$|$\ge 3$| |16|$10^{16}$|$\ge 2$| |17|$10^{18}$|$\ge 3$| |18|$10^{18}$|$\ge 2$| |19|$10^{18}$|$\ge 2$| |20|$10^{18}$|$\ge 2$| Translated by ChatGPT 5