e-olymp
Задачи

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

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

Очень часто возникает задача эффективного вычисления xn по данным x и n, где n - положительное целое число.

Предположим, например, что необходимо вычислить x16. Можно просто начать с x и 15 раз умножить его на x. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя x2, x4, x8, x16.

Эта же идея, в целом, применима к любому значению n следующим образом. Запишем n в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую "1" парой символов SX, а каждый "0" - символом S и вычеркнем крайнюю слева пару символов "SX". Результат представляет собой правило вычисления xn, в котором "S" трактуется как операция возведения в квадрат, а "X" - как операция умножения на x. Например, n = 23 имеет двоичное представление 10111. Таким образом, мы формируем последовательность SXSSXSXSX, из которой удаляем начальную пару SX для получения окончательного правила SSXSXSX. Это правило гласит, что необходимо "возвести в квадрат, возвести в квадрат, умножить на x, возвести в квадрат, умножить на x, возвести в квадрат и умножить на x", т.е. последовательно вычислить значения x2, x4, x5, x10, x11, x22, x23.

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

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

Одно натуральное число n, не превышающее 2·109.

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

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

Лимит времени 1 секунда
Лимит использования памяти 128 MiB
Входные данные #1
23
Выходные данные #1
SSXSXSX
Автор Анатолий Присяжнюк
Источник II этап Всеукраинской олимпиады школьников 2012-2013, г. Бердичев