Возвращает i-е число формата x^y, где x и y — целые числа.

x и y — целые числа больше 1. Специальное число может быть выражено как x^y. Обратите внимание, что специальная числовая последовательность находится в порядке возрастания (4, 8, 9, 16, 25, 27, 32, ...).
Если задано целое число i, программа должна вернуть i-е специальное число.

i=0 -> num=4
i=4 -> num=25

Хотелось бы некоторых инсайтов. Столкнулся с этим в раунде кодирования для компании. Грубая сила закончилась TLE.

Редактировать 1: Найдена ссылка: https://codegolf.stackexchange.com/questions/78985/find-the-n-th-perfect-power.

Edit-2: я поделился ссылкой на codegolf, чтобы помочь проверить некоторые решения, которые уже доступны и, как ожидается, превысят лимит времени. Я пробовал как с решением Mathematica, так и с решением Sage, столкнулся с TLE на обоих из них.


sequence math dynamic-programming wolfram-mathematica exponent
person John Doe    schedule 05.03.2018    source источник
comment
это не по теме. все, что вы сделали, это репост вопроса о коде гольфа без каких-либо усилий для его решения (не говоря уже о том, что там дается однострочное решение по математике)   -  person agentp    schedule 05.03.2018
comment
обратите внимание, что проблема с кодом гольфа допускает x=1, так что это решение требует (тривиальной) настройки.   -  person agentp    schedule 05.03.2018

Ответы (1)


arrow_upward
1
arrow_downward

Эта задача эквивалентна нахождению целого числа j, где log_j k — целое число, а j находится в последовательности с верхней границей k такой, что sum [floor(log_j k) - 1 | j <- [2..floor(sqrt k)] == i

Мы можем сделать грубую оценку того, где будет находиться ith элемент, с помощью бинарного поиска с ограниченной итерацией. Если мы угадаем число в m^2, самое высокое основание, которое может быть подсчитано, будет:

m

Затем мы можем изучить более низкие базы и сложить их количество журналов. Например, i = 10:

Guess: 10^2
Highest base: 10

Then at minimum we have (10 - 1) + (floor(log2 (10^2)) - 1)
= 15 elements. Too many.


Guess: 5^2 
Highest base: 5
Minimum element count: (5 - 1) + (floor(log2 (5^2)) - 1) = 8

Iterate over logs:
  -- Because of the exponential nature of the problem,
  -- if the guess is too large, the bulk of the elements will appear
  -- early in the iteration; and if it's too small, the limit on
  -- exponents will drop early allowing for early exit in either case.

  [floor(logBase x 25) - 1 | x <- [2..4]] = [3,1,1]
  sum ([1] ++ [3,1,1]) = 6. Too few.


Guess: 7^2
Highest base: 7
Minimum element count: (7 - 1) + (floor(log2 (7^2)) - 1) = 10

Iterate over logs:
  [floor(logBase x 49) - 1 | x <- [2..6]] = [4,2,1,1,1]
  sum ([1] ++ [4,2,1,1,1]) = 10

Answer: 7^2
person גלעד ברקן    schedule 06.03.2018