e-olymp 2814. Быстрое возведение в степень.

Задача

Быстрое возведение в степень

Быстрое возведение в степень

Очень часто возникает задача эффективного вычисления $x^{n}$ по данным $x$ и $n$, где $n$ — положительное целое число.
Предположим, например, что необходимо вычислить $x^{16}$. Можно просто начать с $x$ и 15 раз умножить его на $x$. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя $x^{2}$, $x^{4}$, $x^{8}$, $x^{16}$.
Эта же идея, в целом, применима к любому значению $n$ следующим образом. Запишем $n$ в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую «1» парой символов SX, а каждый «0» — символом S и вычеркнем крайнюю слева пару символов SX. Результат представляет собой правило вычисления $x^{n}$, в котором «S» трактуется как операция возведения в квадрат, а «X» — как операция умножения на $x$. Например, $n = 23$ имеет двоичное представление $10111$. Таким образом, мы формируем последовательность SXSSXSXSX, из которой удаляем начальную пару SX для получения окончательного правила SSXSXSX. Это правило гласит, что необходимо «возвести в квадрат, возвести в квадрат, умножить на $x$, возвести в квадрат, умножить на $x$, возвести в квадрат и умножить на $x$», т.е. последовательно вычислить значения $x^{2}$, $x^{4}$, $x^{5}$, $x^{10}$, $x^{11}$, $x^{22}$, $x^{23}$.

Вам нужно для заданного n сформулировать соответствующее правило быстрого возведения числа $x$ в степень $x^{n}$

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

Одно натуральное число $n$, не превышающее $2 \cdot 10^{9}$.

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

Выведите строку для правила возведения числа $x$ в степень $n$ для получения $x^{n}$.

Тесты

# Входные данные Выходные данные
1 23 SSXSXSX
2 1
3 16 SSSS
4 1000000 SXSXSXSSXSSSSSXSSSXSSSSSS
5 2018 SXSXSXSXSXSSSSXS

Решение

С помощью первого цикла while в переменную $k$ записываем перевернутый двоичный код числа $n$. Переменную $c$ используем как счётчик кол-ва бит в $n$. Во втором цикле while выводим S или SX если правый бит $0$ или $1$ соответственно, теряя при это последнюю $1$ как и сказано по условию задачи.

Условие задачи можно найти на e-olymp
Код решения — ideone

Related Images:

4 thoughts on “e-olymp 2814. Быстрое возведение в степень.

  1. Сначала критика Вашего решения.
    — Зачем строить сначала инвертированную строка, потом ее переворачивать? Новые символы можно добавлять в начало.
    — Зачем переводить в двоичную систему? Компьютер уже хранит в двоичной системе.
    — Нельзя использовать строки — это задача на циклы. Строки мы учили позже.
    Мне нравится рекурсивное решение этой задачи. Приведу его, возможно оно подскажет как решать одним циклом без string:

    Ваше решение должно быть с циклами, а не с рекурсией. Но принцип работы с двоичным представлением числа и битовыми операциями сохраняется. Моя версия с циклами уместилось в 8 строк и 182 байт. Ваше не должно быть намного длиннее.

  2. Здравствуйте, Никита!
    Рад, что Вы снова проявили интерес к предмету. Я Вас отлично помню, хотя и долго искал в своих записях, когда же это выдал вам задачу. Задача оказалась за сентябрь позапрошлого года. Как же быстро пролетели эти годы!
    Я расчитывал получить от вас такое решение:

    Но ваш вариант тоже хорош для практики.
    Пожалуйста, посмотрите на первую строку условия задачи. Нам точно нужно вычислить xn?

Добавить комментарий