The k-th root
For each pair of numbers x and k, find the largest integer r with rk ≤ x. That is the integer part of the k-th root of x. One line of code seems enough—but the numbers go up to 10¹⁸, more than ordinary floating point remembers.
Input
The first line holds the number of queries q (1 ≤ q ≤ 10,000). Each of the next q lines holds integers x and k (0 ≤ x ≤ 10¹⁸, 1 ≤ k ≤ 60).
Output
For each query, the number r on a line of its own.
Examples
Example 1
7 10 2 16 2 27 3 26 3 1000000000000000000 2 1 60 0 7
3 4 3 2 1000000000 1 0
Limits
- Time · Python
- 5000 ms
- Time · Go
- 1000 ms
- Memory
- 256 MB
- Judging
- 5 tests
Walkthrough
Open it step by step: each step gives away a little more. You can jump straight to the solution, but a problem solved with one hint stays with you longer.
1Hint 1
Try int(999999999999999999 ** 0.5) in Python. The right answer is 999,999,999, because (10⁹)² = 10¹⁸ is already larger. What does floating point return?
2Hint 2
As r grows, the question “rk ≤ x?” first answers “yes” and then only “no”. Which algorithm looks for the place where the answer changes?
3The idea
The number 999,999,999,999,999,999 does not fit in the 53 bits of a double's mantissa, and converting it to float rounds it to exactly 10¹⁸. Its root is exactly 10⁹—one more than the truth. So we compute in integers: look for the largest r with rk ≤ x by binary search on r. The predicate is monotone and the comparison exact.
4Walkthrough
Keep the invariant lok ≤ x < hik. Start with lo = 0 and hi = 1 and double hi while hik ≤ x—that is how the upper bound finds itself (this is exponential search). Then an ordinary binary search while hi − lo > 1. The answer is lo.
In Python mid ** k is exact at any size. In Go, uint64 overflows already at 2⁶⁴, so raise to the power one factor at a time and stop as soon as the product exceeds x: checking p > x / r before multiplying guarantees there is no overflow.
You can be faster: take an approximation from floating point and correct it by ±1–2 with an integer check. But binary search is shorter to prove right, and 60 steps per query are nothing.
4+Solution
5Complexity
Doublings and search steps: O(log r) ≤ 60; each check is O(k) multiplications. In all O(q · k · log x), a few tens of millions of operations at worst—but for large k the root r itself is small and the steps are few.
6Common mistakes
- int(x ** (1/k)). Off by one near exact powers, especially for large x. Tests 2 and 3 are packed with such numbers.
- Overflow in Go.
mid*midfor mid around 10¹⁰ no longer fits in uint64, and the comparison “≤ x” answers “yes” on garbage. - k = 1 and x = 0. The answers are x and 0—check that your doubling loop does not run forever or start from hi = 0.