Задача №115264. Степенные числа
Если вас интересует математика, то эта задача для вас.
Будем называть целое число \(n\) \(k\)-степенным , если его можно разложить в сумму различных степеней числа \(k\), то есть если \(n\) представимо в виде \(n = k^{a_1} + k^{a_2} + \ldots + k^{a_d}\), где все \(a_i\) целые и \(a_i \ne a_j\) для всех \(i \ne j\).
Ответьте на множество запросов: какое минимальное целое число, большее либо равное \(n_i\), является \(k_i\)-степенным?
Первая строка ввода содержит целое число \(q\) — количество запросов, на которые вам предстоит ответить (\(1 \le q \le 10^5\)).
Каждая из следующих \(q\) строк содержит два целых числа \(n_i\) и \(k_i\), описывающие \(i\)-й запрос (\(1 \le n_i \le 10^9\); \(2 \le k_i \le 10^9\)).
Выведите \(q\) строк, в \(i\)-й из которых выведите минимальное \(k_i\)-хорошее число, большее либо равное \(n_i\).
Баллы за каждую подзадачу начисляются только в случае, если все тесты для этой подзадачи и необходимых подзадач успешно пройдены.
| Подзадача | Баллы | Ограничения | Необходимые подзадачи | Информация о проверке |
| 0 | – | примеры из условия | полная | |
| 1 | 6 | \(n_i \le 10^5\), \(k_i = 2\) для всех \(i\) | первая ошибка | |
| 2 | 9 | \(n_i \le k_i\) для всех \(i\) | первая ошибка | |
| 3 | 10 | \(q = 1\); \(n_i \le 10^5\) для всех \(i\) | полная | |
| 4 | 11 | \(n_i \le 10^5\), \(k_i = 10\) для всех \(i\) | первая ошибка | |
| 5 | 13 | \(n_i \le 10^5\) для всех \(i\); \(k_i = k_j\) для всех \(i, j\) | 1, 4 | первая ошибка |
| 6 | 16 | \(q \le 500\); \(k_i \ge 20\) для всех \(i\) | первая ошибка | |
| 7 | 35 | без дополнительных ограничений | 0 – 7 | первая ошибка |
7 1 2 2 3 6 5 13 10 14 3 3620 12 10000 3
1 3 6 100 27 20736 19683