Статья Автор: Деникина Н.В., Деникин А.В.

1.1 Дробные системы счисления — последние цифры как остаток по модулю

Последние цифры — это остаток

У целого числа X, записанного в системе p, последние m цифр — это в точности остаток X по модулю p^m, записанный m цифрами (при необходимости с ведущими нулями). Причина простая: старшие разряды весят p^m и больше, то есть делятся на p^m нацело и на остаток не влияют.

последние 1 цифра в 16-ричной  ->  X mod 16
последние 2 цифры в 16-ричной  ->  X mod 256
последние 3 цифры в 8-ричной   ->  X mod 512

Мост к дробям

В прошлой тетради мы выяснили: цифры после запятой у (M / p^k)^N — это цифры целого M^N, прижатые вправо. Прижаты вправо — значит последние цифры дроби и последние цифры целого M^N это одно и то же. Складываем два факта:

последние m цифр записи (0,d1...dk)^N = M^N mod p^m

Задача про дробь превратилась в задачу про остаток. Это и есть тот самый аналитический шаг, без которого программа бессильна: возвести 171 в степень миллиард нельзя, а взять остаток — можно.

▶ Запустите. Первая строка считается мгновенно, хотя показатель — миллиард.

N = 10 ** 9

# так — мгновенно: остаток считается по ходу возведения в степень
print(pow(171, N, 256))

# а так нельзя: у 171**N примерно 1,8 миллиарда шестнадцатеричных цифр
# print(171 ** N % 256)

digits = "0123456789ABCDEF"
r = pow(171, N, 256)
print(digits[r // 16] + digits[r % 16])

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

1
01

Функция pow с тремя аргументами не строит огромное число: она возводит в степень по модулю, беря остаток на каждом шаге. Закомментированная строка не отработала бы никогда — у числа 171^1000000000 примерно 1,8 миллиарда шестнадцатеричных цифр.

digits = "0123456789ABCDEF"

def frac_tail(mant, p, N, m):
    """последние m цифр дробной записи (0,mant)^N в системе p"""
    M = 0
    for ch in mant:
        M = M * p + digits.index(ch)
    r = pow(M, N, p ** m)
    s = ""
    for i in range(m):
        s = digits[r % p] + s
        r = r // p
    return s

print(frac_tail("AB", 16, 5, 2))
print(frac_tail("AB", 16, 1000000007, 2))
print(frac_tail("53", 8, 1000, 3))

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

3B
23
341

Заметьте, ответ выводится ровно m цифрами. Ведущий ноль в ответе — не украшение: «01» и «1» это разные ответы, и на олимпиаде второй не засчитают.

Запишите две последние цифры шестнадцатеричной записи числа (0,AB₁₆)⁵. Ровно две цифры подряд, заглавными буквами.

Проверить ответ

Какое выражение даст две последние шестнадцатеричные цифры числа (0,AB₁₆)^N при N = 10⁹?

Проверить ответ

Какая цифра стоит последней в восьмеричной записи числа (0,53₈)¹⁰⁰⁰?

Проверить ответ

Сопоставьте вопрос и модуль, по которому нужно считать остаток.

Проверить ответ

Верно или неверно?

Проверить ответ

Итог: любой вопрос про хвост записи сводится к остатку. Но на олимпиаде показатель бывает такой, что и pow посчитать негде — например, его дают в виде 20 000 000 000. Тогда работает следующий приём: период.

Загрузка...

Чтобы оставить комментарий, необходимо авторизоваться

💬

Пока нет комментариев. Будьте первым!

Печать