Быстрое возведение в степень
Быстрое возведение в степень
Очень часто возникает задача эффективного вычисления 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
.
23
SSXSXSX