1.1 Дробные системы счисления — период последних цифр и свёртка показателя

Хвост записи повторяется

Остатков по модулю 256 всего 256 штук, поэтому последовательность M, M², M³, ... по модулю 256 обязана зациклиться. Если M нечётно, у него есть обратный по модулю 256, и цикл начинается сразу с первого члена: последовательность чисто периодическая. Длина этого цикла называется порядком M по модулю 256.

Полезный факт про степени двойки: для любого нечётного M верно M⁶⁴ = 1 (mod 256). Значит порядок всегда делит 64 — он равен 1, 2, 4, 8, 16, 32 или 64, и ничему другому.

Как найти порядок руками

Возводим в квадрат и каждый раз оставляем две последние шестнадцатеричные цифры. Одно действие — умножение двух двузначных чисел в столбик:

AB -> 39 -> B1 -> 61 -> C1 -> 81 -> 01

Это 171², 171⁴, 171⁸, 171¹⁶, 171³², 171⁶⁴ по модулю 256. На шестом шаге получили 01, то есть единицу: порядок 171 по модулю 256 равен 64.

Программа печатает:

AB -> 39 -> B1 -> 61 -> C1 -> 81 -> 01 -> 01
порядок: 64
N mod 64 = 0
ответ: 01

Полный разбор олимпиадной задачи

Найти две последние цифры шестнадцатеричной записи числа (0,AB₁₆)^N при N = 20 000 000 000.

1. 0,AB₁₆ = 171/256, значит (0,AB₁₆)^N = 171^N / 16^2N.
2. Запись конечна, после запятой 2N цифр, и это цифры целого 171^N.
3. Две последние цифры = 171^N mod 256.
4. Порядок 171 по модулю 256 равен 64.
5. N = 2·10¹⁰ = 2¹¹·5¹⁰, а 2¹¹ = 2048 делится на 64. Значит N кратно 64 и 171^N = 1 (mod 256).
6. Единица по модулю 256 в двух шестнадцатеричных цифрах — это 01.

Ответ: 01. Пункт 5 — единственное место, где нужна арифметика олимпиадного уровня: разложить показатель на множители и увидеть в нём 2¹¹.

Про последнее утверждение — следующая тетрадь: чётная мантисса ведёт себя принципиально иначе, и наивное применение остатка там даёт формально верный, но бессодержательный ответ.