Форум: «ЕГЭ по информатике»

откуда задача? очень похоже на задачу олимпиады ИТМО прошлого года
Число, записанное в четверичной системе счисления как 323₄, возвели в степень, записанную в четверичной системе счисления как 232₄. Определите и запишите в ответ подряд без пробелов последние две цифры результата возведения в степень, записанного в четверичной системе счисления.
Ответ: 21
Решение
Возведение в степень натурального числа есть множественное умножение его на само себя. Обратим внимание, что при перемножении двух натуральных чисел последняя цифра результата зависит только от значений последних цифр перемножаемых чисел. В условии задания требуется определить последние две цифры результата возведения в степень четверичного числа, но мы воспользуемся тем, что исходное число в четверичной системе счисления можно перевести в шестнадцатеричную систему счисления и тогда последние две цифры его четверичной записи будут однозначно соответствовать одной последней цифре его шестнадцатеричной записи: 323₄ = 3B₁₆.
Теперь рассмотрим первые несколько степеней этого числа (отметит, что при решении задания достаточно было получать только последние цифры):
3B₁₆¹=3B₁₆
3B₁₆²=3B₁₆*3B₁₆=D99₁₆
3B₁₆³= D99₁₆*3B₁₆=32243₁₆
3B₁₆⁴=32243₁₆*3B₁₆=B8E571₁₆
3B₁₆⁵= B8E571₁₆*3B₁₆=2A9CE10B₁₆
Обратим внимание, что после возведения в пятую степень последняя цифра оказалась опять B, как уже было при возведении в первую степень. Поскольку умножаем мы на одно и то же число, а последняя цифра зависит только от последних цифр сомножителей, можно сделать вывод, что последние цифры будут образовывать цикл из четырех значений: B-9-3-1. Значит для того, чтобы определить, какая цифра будет в результате возведения числа 3B₁₆ в степень 232₄=46₁₀ можно посчитать остаток от деления 46 на 4. Остаток равен 2, следовательно, последняя цифра в записи числа в шестнадцатеричной системе счисления будет второй цифрой цикла, то есть 9. Осталось перевести 9₁₆ в четверичную систему счисления и получить 21₄. Значит в конце четверичной записи результата возведения в степень будет последовательность цифр 21.