409776: GYM103741 F K-th Power
Memory Limit:256 MB
Time Limit:1 S
Judge Style:Text Compare
Creator:
Submit:0
Solved:0
Description
F. K-th Powertime limit per test1.5 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output
Walk_alone hates numbers with large exponents, and he considers an integer $$$x$$$ as good if and only if there does not exist a prime number $$$p$$$, such that $$$x$$$ is a multiple of $$$p^k$$$. He hopes to find the number of all good integers in range $$$[l,r]$$$.
InputThe only line of input contains three integers $$$l,r\ (1 \leq l \leq r \leq 10^{14})$$$ and $$$k\ (2 \leq k \leq 10^9)$$$, indicating the lower range, upper range of the querying interval and the asked $$$k$$$ mentioned above.
OutputOutput a single integer indicating the number of good integers in range of $$$[l,r]$$$.
ExampleInput1 10 2Output
7Note
In the example above, $$$4$$$ and $$$8$$$ are multiples of $$$2^2$$$, and $$$9$$$ is a multiple of $$$3^2$$$.