Швидке піднесення до степеня

Дуже часто виникає задача ефективного обчислення x^n для заданих $x$ та $n$, де $n$ — додатне ціле число.

Наприклад, нехай потрібно обчислити x^{16}. Можна просто почати з $x$ і перемножувати його на $x$ ще $15$ разів. Однак той самий результат можна отримати лише чотирма множеннями, якщо повторно підносити до квадрату, послідовно обчислюючи 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}.

Потрібно побудувати правило для швидкого піднесення $x$ до степеня $n$ для заданого $n$.