Возьмите все 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
Примеры
Ввод:
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.
Ввод:
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. Следуйте условию и ограничениям выше.