Задача

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

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

#include <iostream>

using namespace std;

int main() {
    long long n, k = 0;
    cin >> n;
    int c = 0;
    while (n > 1) {
        long long bit = n & 1;
        n >>= 1;
        k <<= 1;
        k |= bit;
        c += 1;
    }
    while (c--) {
        long long bit = k & 1;
        k >>= 1;
        cout << (bit == 0 ? "S" : "SX");
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, k = 0;

cin >> n;

int c = 0;

while (n > 1) {

long long bit = n & 1;

n >>= 1;

k <<= 1;

k |= bit;

c += 1;

}

while (c--) {

long long bit = k & 1;

k >>= 1;

cout << (bit == 0 ? "S" : "SX");

}

return 0;

}

Решение

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

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

Related Images:

Похожее

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

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

#include <iostream>
void f(unsigned n) {
    if (n > 1) {
        f(n >> 1);
        std::cout << (n & 1U? "SX" : "S");
    }
}
int main() {
    unsigned n;
    std::cin >> n;
    f(n);
    return 0;
}

#include <iostream>

void f(unsigned n) {

if (n > 1) {

f(n >> 1);

std::cout << (n & 1U? "SX" : "S");

}

int main() {

unsigned n;

std::cin >> n;

f(n);

return 0;

}

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

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

#include <iostream>
int main() {
    unsigned n, m = 0x80000000;
    std::cin >> n;
    while ( !(m & n)) m >>= 1;
    while ( m >>= 1 > 0 ) std::cout << (n & m? "SX" : "S");
}

#include <iostream>

int main() {

unsigned n, m = 0x80000000;

std::cin >> n;

while ( !(m & n)) m >>= 1;

while ( m >>= 1 > 0 ) std::cout << (n & m? "SX" : "S");

}

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

Никита Пушкин says: 31/03/2019 at 13:12

Спасибо, исправил первую строку условия
Мазурок Игорь Евгеньевич says: 31/03/2019 at 19:37

Хорошо. Можно приступать к следующей.