Корень k-й степени
Для каждой пары чисел x и k найдите наибольшее целое r, для которого rk ≤ x. Это целая часть корня k-й степени из x. Кажется, что хватит одной строчки — но числа доходят до 10¹⁸, а это больше, чем помнит обычная плавающая точка.
Вход
В первой строке число запросов q (1 ≤ q ≤ 10 000). В каждой из следующих q строк — целые x и k (0 ≤ x ≤ 10¹⁸, 1 ≤ k ≤ 60).
Выход
Для каждого запроса — число r в отдельной строке.
Примеры
Пример 1
7 10 2 16 2 27 3 26 3 1000000000000000000 2 1 60 0 7
3 4 3 2 1000000000 1 0
Ограничения
- Время · Python
- 5000 мс
- Время · Go
- 1000 мс
- Память
- 256 МБ
- Проверка
- 5 тестов
Разбор
Открывайте по ступеням: каждая следующая подсказывает больше. Можно сразу к решению — но задача, решённая с одной подсказкой, запоминается лучше.
1Подсказка 1
Проверьте int(999999999999999999 ** 0.5) в Python. Правильный ответ — 999 999 999, потому что (10⁹)² = 10¹⁸ уже больше. Что вернёт плавающая точка?
2Подсказка 2
Вопрос «rk ≤ x?» при росте r сначала отвечает «да», потом только «нет». Какой алгоритм ищет место, где ответ меняется?
3Идея
Число 999 999 999 999 999 999 не помещается в 53 бита мантиссы double, и при переводе в float оно округляется до ровно 10¹⁸. Корень из этого — ровно 10⁹, на единицу больше правды. Поэтому считаем в целых числах: ищем наибольшее r с rk ≤ x двоичным поиском по r. Предикат монотонен, а сравнение точное.
4Разбор
Держим инвариант lok ≤ x < hik. Начинаем с lo = 0 и hi = 1 и удваиваем hi, пока hik ≤ x — так верхняя граница находится сама (это экспоненциальный поиск). Затем обычный двоичный поиск, пока hi − lo > 1. Ответ — lo.
В Python степень mid ** k точная при любом размере. В Go uint64 переполнится уже на 2⁶⁴, поэтому возводим в степень по одному множителю и останавливаемся, как только произведение превысило x: проверка p > x / r перед умножением гарантирует, что переполнения не будет.
Можно и быстрее: взять приближение из плавающей точки и поправить его на ±1–2 целочисленной проверкой. Но двоичный поиск короче доказать, а 60 шагов на запрос — пустяк.
4+Решение
5Сложность
Удвоений и шагов поиска — O(log r) ≤ 60, каждая проверка — O(k) умножений. Итого O(q · k · log x), в худшем случае несколько десятков миллионов операций — но при больших k само r маленькое, и шагов мало.
6Типичные ошибки
- int(x ** (1/k)). Ошибается на единицу возле точных степеней, особенно для больших x. Тесты 2 и 3 набиты именно такими числами.
- Переполнение в Go.
mid*midдля mid около 10¹⁰ уже не помещается в uint64, и сравнение «≤ x» отвечает «да» на мусоре. - k = 1 и x = 0. Ответы x и 0 — проверьте, что ваш цикл удвоения не уходит в бесконечность и не начинает с hi = 0.