Последние новости
03.04.24
Предварительные результаты финального тура
05.03.24
Проведение финального тура
01.01.24
Предварительные результаты
25.12.23
Отборочный этап завершён.
18.12.23
Отборочный этап продлён по 24 декабря включительно
Опишите алгоритм возведения числа a в 255 степень с помощью только операции умножения:
11.1 За 14 операций умножения без использования дополнительной памяти (то есть разрешается использовать только исходное число и результат последней операции).
11.2 За 10 операций умножения с использованием любого количества дополнительной памяти.
11.3 За 10 операций умножения с использованием одной ячейки дополнительной памяти (то есть помимо исходного числа и результата последней операции, разрешается держать в памяти ещё одно число. Это число может меняться в процессе работы алгоритма).
Замечание: верное решение для 11.3 будет засчитываться и для 11.2.
11.1) 1) a * a = a^2 2) a^2 * a = a^3 3) a^3 * a^3 = a^6 4) a^6 * a = a^7 5) a^7 * a^7 = a^14 6) a^14 * a = a^15 7) a^15 * a^15 = a^30 8) a^30 * a = a^31 9) a^31 * a^31 = a^62 10) a^62 * a = a^63 11) a^63 * a^63 = a^126 12) a^126 * a = a^127 13) a^127 * a^127 = a^254 14) a^254 * a = a^255 11.3) 1) a * a = a^2 2) a^2 * a^2 = a^4 3) a^4 * a = a^5 4) a^5 * a^5 = a^10 (a^5 храним) 5) a^10 * a^5 = a^15 (a^15 храним) 6) a^15 * a^15 = a^30 7) a^30 * a^30 = a^60 8) a^60 * a^60 = a^120 9) a^120 * a^120 = a^240 10) a^240 * a^15 = a^255