Дробные числа

Продвинутые приёмы для олимпиады

Трюк с тетрадами (hex ↔ bin) работает по обе стороны от запятой. Каждая hex-цифра после запятой — это ровно 4 двоичных цифры после запятой.

пример// hex → bin: тетрады для дробной части
0,C8₁₆  →  0, 1100 1000₂  =  0,11001₂

// bin → hex: группируем по 4 СПРАВА от запятой
0,101110₂  →  0, 1011 1000₂  =  0,B8₁₆
                         ↑ дополнили нулями справа

Олимпиадный приём: если задача даёт hex-дробь и просит что-то в двоичной — поцифренный перевод мгновенный, не нужна арифметика.

Не все дроби — чистые периоды. Бывает предпериод (конечная часть перед периодом):

Как перевести в обыкновенную дробь

Трюк: записать два числа — «всё вместе без запятой» и «предпериод без запятой», вычесть, разделить на нужное количество девяток и нулей.

пример// 0,1(6)₁₀ = ?
// Пусть x = 0,16666...
//  10x =  1,6666...
// 100x = 16,6666...
// 100x − 10x = 15
//  90x = 15  →  x = 15/90 = 1/6

// Или формулой:
0,1(6) = (16 − 1) / 90 = 1/6
           ↑       ↑
    «16» − «1»   одна 9 + один 0

На ИТМО напрямую предпериод спрашивают редко, но без этого приёма нельзя проверить ответ при переводе.

Ловушка 1: 0,(макс. цифра) = 1

факт0,(9)₁₀ = 9/9   = 1    «ноль целых, 9 в периоде» = 1
0,(F)₁₆ = 15/15 = 1    та же идея для hex
0,(1)₂  = 1/1   = 1    в двоичной макс. цифра = 1
0,(7)₈  = 7/7   = 1    в восьмеричной

// это не парадокс — просто другая запись того же числа

Ловушка 2: 0,1₁₀ — бесконечна в двоичной

Знаменатель 10 = 2 · 5. Делитель 5 не делит 2 ⇒ период. В двоичной: 0,1₁₀ = 0,0(0011)₂. Именно поэтому 0.1 + 0.2 ≠ 0.3 в компьютерах.

Ловушка 3: 1/3 записывается красиво в hex

факт// Формула: 0,(d)₁₆ = d/15
// Нужно: d/15 = 1/3  ⇒  d = 5

1/3 = 0,(5)₁₆
2/3 = 0,(A)₁₆    // A = 10, 10/15 = 2/3

// сравни с десятичной: 1/3 = 0,(3)₁₀ — 3/9 = 1/3
// принцип один: цифра = числитель · (b−1) / знаменатель

Ловушка 4: «конечная в base 10» ≠ «конечная везде»

1/3 конечна в base 12, потому что 12 = 2² · 3, а знаменатель 3 делит 12. То есть 1/3 = 0,4₁₂. Проверка: 4/12 = 1/3 ✓.

Длина периода дроби 1/q в системе с основанием b — это наименьшее k, при котором b^k ≡ 1 (mod q). Это называется «мультипликативный порядок b по модулю q».

примеры// 1/7 в десятичной: порядок 10 mod 7
10¹ mod 7 = 3
10² mod 7 = 2
10³ mod 7 = 6
10⁴ mod 7 = 4
10⁵ mod 7 = 5
10⁶ mod 7 = 1  ← первый раз!  Период = 6

// Проверка: 1/7 = 0,(142857) — ровно 6 цифр ✓

Следствие: если b ≡ 1 (mod q), то 1/q — чистый однозначный период. Если q делит b, то 1/q конечна. Если ни то ни другое — период длиннее 1.

На ИТМО это знание помогает быстро оценить, будет ли дробь «красивой» в данной системе.

Это самый частый паттерн задачи 1 финала ИТМО. Разберём полностью.

Постановка задачи (типа финала 2023)

Дано: (0,AB₁₆)². Найти все hex-цифры дробной части.

Шаг 1. Превращаем в обыкновенную

шаг 10,AB₁₆ = AB₁₆ / 16² = 171 / 256

Шаг 2. Возводим в степень

шаг 2(171/256)² = 171² / 256² = 29241 / 65536

// 65536 = 16⁴ ⇒ в hex-записи будет 4 цифры после запятой

Шаг 3. Переводим числитель в hex

шаг 329241 ÷ 16 = 1827  ост 9  ↑
 1827 ÷ 16 =  114  ост 3  ↑
  114 ÷ 16 =    7  ост 2  ↑
    7 ÷ 16 =    0  ост 7  ↑

29241₁₀ = 7239₁₆

Шаг 4. Собираем ответ

ответ(0,AB₁₆)² = 7239₁₆ / 10000₁₆ = 0,7239₁₆

// hex-цифры дробной части: 7, 2, 3, 9
// сумма цифр: 7 + 2 + 3 + 9 = 21
// последняя цифра: 9

Ключевое наблюдение для больших N

python# Последние 2 hex-цифры (0,AB)^N
N = 20_000_000_014
result = pow(171, N, 256)   # 171^N mod 16²
print(hex(result))          # мгновенно!