Все задачи
Легко Решено: 0 Процент решений: 0%

Различные степени

Посчитайте различные значения a в степени b, где a и b берутся из диапазона.

Чему вы научитесь

  • Сводить основание к наименьшему корню
  • Сравнивать огромные степени, не вычисляя их
  • Считать уникальные значения с помощью множества

Условие

Возьмите все a и все b от lo до hi и вычислите a^b. Некоторые значения повторяются, например 2^4 = 4^2 = 16. Посчитайте, сколько получается различных значений. Сами значения огромны, но вычислять их и не нужно: запишите a как r^k, где r сам не является точной степенью, тогда a^b = r^(k × b). Две степени равны ровно тогда, когда у них одинаковое r и одинаковый показатель k × b.

Реализуйте distinct_powers(lo, hi).

Входные данные

lo: наименьшее основание и наименьший показатель.

hi: наибольшее основание и наибольший показатель.

Выходные данные

Верните количество различных значений a^b при lo ≤ a ≤ hi и lo ≤ b ≤ hi.

Ограничения

2 ≤ lo ≤ hi ≤ 100

Примеры

Пример 1
Ввод:
lo = 2
hi = 4

Ожидаемый вывод:
expected = 8
Ввод:
long long lo = 2;
long long hi = 4;

Ожидаемый вывод:
long long expected = 8;
Ввод:
long lo = 2;
long hi = 4;

Ожидаемый вывод:
long expected = 8;

Пояснение

Девять степеней: 4, 8, 16, 9, 27, 81, 16, 64, 256. Число 16 встречается дважды, поэтому различных значений 8.

Пример 2
Ввод:
lo = 7
hi = 7

Ожидаемый вывод:
expected = 1
Ввод:
long long lo = 7;
long long hi = 7;

Ожидаемый вывод:
long long expected = 1;
Ввод:
long lo = 7;
long hi = 7;

Ожидаемый вывод:
long expected = 1;

Пояснение

Есть только 7^7, поэтому 1.

Как подступиться

Сначала попробуйте сами, затем открывайте подсказки по одной.

Подсказка 1

Найдите наименьшее r и наибольшее k, для которых r^k = a.

Подсказка 2

a^b равно r^(k × b), поэтому пара (r, k × b) однозначно задаёт значение.

Подсказка 3

Сложите пары в множество и посчитайте их.

Ожидаемая сложность

время O((hi − lo)² log hi), доп. память O((hi − lo)²)

Ссылки

Это задание адаптировано для CodeUtility. Следуйте условию и ограничениям выше.

Лучшее принятое решение каждого участника. Более быстрые, экономные и высоко оценённые решения стоят выше.

Принятых решений пока нет. Решите задачу и займите первое место.

Учитесь у других

Решения сообщества

Пока нет опубликованных решений. Решите задание, чтобы поделиться первым.