Теория
Что нужно знать
Задание 14 проверяет системы счисления: перевод чисел, арифметику в разных основаниях и разбор записи числа по цифрам. В базе Kompege по этой теме 1 377 задач, 121 решение (115 программных) и 287 видеоразборов. Тема сохраняется в 2027 году без изменения номера.
Позиционная запись
В системе счисления с основанием p используются цифры от 0 до p − 1. Значение числа складывается из цифр, умноженных на степени основания: чем левее цифра, тем больше её вес. Цифры после 9 обозначают латинскими буквами: A = 10, B = 11, …, F = 15, Z = 35.
- Основание p показывает, во сколько раз вес следующего разряда больше предыдущего.
- Цифра не может быть больше или равна основанию: в семеричной записи нет цифры 7.
- В основании 2 допустимы только 0 и 1, в основании 16 — 0–9 и A–F.
- Если основание больше 36, в условии отдельно задают обозначения цифр.
- Ведущие нули не меняют значение, но могут изменить количество разрядов.
N = d_k·p^k + d_{k−1}·p^{k−1} + … + d_1·p + d_00 ≤ d_i ≤ p − 1
Перевод в десятичную
Значение числа считают по развёрнутой записи. Схема Горнера делает то же самое без степеней: начинаем с нуля, для каждой цифры умножаем накопленный результат на p и прибавляем цифру.
- Схема Горнера: (((d_k·p + d_{k−1})·p + d_{k−2})·p + …)·p + d_0.
- В Python строку без неизвестных переводит int(s, p); буквы A–Z понимаются как 10–35.
- Для неизвестной цифры строку собирают после подстановки или считают коэффициенты вручную.
- Проверка: число цифр и старшая цифра должны соответствовать основанию.
N = ((…((d_k·p + d_{k−1})·p + d_{k−2})·p + …)·p + d_0)int("2A7", 16) = 679
Перевод из десятичной
Чтобы перевести целое число в основание p, делят его на p с остатком, пока результат не станет нулём. Остатки, записанные в обратном порядке, дают цифры числа.
- Остаток от деления — очередная младшая цифра.
- Частное становится новым числом для следующего шага.
- Остатки выписывают снизу вверх: последний остаток — старшая цифра.
- Ноль записывают одной цифрой 0.
- Проверка: обратный перевод должен дать исходное число.
d_i = n mod pn ← n div p679_10 = 10204_5
Количество разрядов и границы
k-значное число в основании p лежит в полуинтервале от p^{k−1} до p^k. Это позволяет находить основание по количеству цифр и наоборот.
- p^{k−1} ≤ N < p^k — ровно k цифр.
- Трёхзначность: p^2 ≤ N < p^3.
- Наименьшее основание для k цифр: p = ⌊N^{1/(k−1)}⌋ + 1 с проверкой.
- Старшая цифра d: d·p^{k−1} ≤ N < (d + 1)·p^{k−1}.
- Для N = 6^30 и трёх цифр: p^2 ≤ 6^30 < p^3, значит p ≈ 6^15.
p^{k−1} ≤ N < p^kk = ⌊log_p N⌋ + 1
Основания 2, 4, 8, 16
Если одно основание — степень другого, перевод делают группами битов. Одна шестнадцатеричная цифра — это 4 бита, восьмеричная — 3 бита, четверичная — 2 бита.
- 16 = 2^4: каждой цифре 0–F соответствует ровно 4 бита.
- 8 = 2^3: каждой цифре 0–7 — 3 бита.
- 4 = 2^2: каждой цифре 0–3 — 2 бита.
- Группы набирают справа налево; в старшей группе ведущие нули отбрасывают.
- Обратный перевод: двоичную запись разбивают на группы по 3 или 4 бита.
4FDC_16 = 0100 1111 1101 1100_214206_8 = 001 100 010 000 110_2
Арифметика в основании p
Сложение, вычитание и умножение выполняют поразрядно, но перенос и заём равны p, а не 10. Умножение на p сдвигает запись на один разряд влево и дописывает ноль.
- При сложении цифр: если сумма ≥ p, записываем сумму − p и переносим 1.
- При вычитании: если уменьшаемое меньше, занимаем p у старшего разряда.
- Умножение на p — сдвиг влево; деление на p — сдвиг вправо.
- Сложение и вычитание удобно проверять переводом в десятичную.
- Нельзя складывать цифры разных оснований без перевода.
a + b = c + carry·pa − b = c − borrow·p
Неизвестная цифра
Если цифра x встречается в записи, выражение линейно по x: каждое вхождение даёт x·p^r, где r — позиция разряда. Поэтому E(x) = A + B·x, и перебор нужен только по допустимым цифрам.
- x — цифра основания p: 0 ≤ x ≤ p − 1.
- Если x стоит первой цифрой, то 1 ≤ x ≤ p − 1.
- Если в условии x > 0, ноль исключается.
- Коэффициент B — сумма p^r по всем позициям, где стоит x.
- Для двух цифр x и y перебирают пары; порядок и ограничения проверяют отдельно.
- Перебор p ≤ 40 — это не более 40 значений, его всегда можно написать.
E(x) = A + B·xE(x) ≡ 0 (mod m)
Неизвестное основание
Основание p должно быть больше каждой цифры, встречающейся в записи. Если p входит в веса разрядов, значение выражения — многочлен от p; его проверяют перебором от максимальной цифры плюс один.
- Минимальное основание: p > максимальная цифра в записи.
- Для цифры Z минимальное основание 36, для F — 16.
- Если операнды в разных основаниях, для каждого своё ограничение.
- Основание может быть больше 36; тогда цифры задаются условием.
- Ищите наименьшее p с нужным остатком и не забывайте про верхнюю границу перебора.
p ≥ max(d_i) + 1N(p) = d_k·p^k + … + d_0
Анализ цифр записи
Многие задачи просят не число, а характеристику его записи: количество заданных цифр, сумму цифр, самую частую цифру, длину серии одинаковых цифр или палиндромность.
- Количество цифр d: считайте остатки n % p при переводе.
- Сумма цифр: складывайте остатки.
- Самая частая цифра: collections.Counter или max(a, key=a.count).
- Серия одинаковых цифр: сравнивайте соседние элементы.
- Палиндром: s == s[::-1]; для перестановок — не более одной нечётной частоты.
- Цифры больше 9 сравнивайте по числовому значению, а не по символу.
count(d) = |{i : d_i = d}|sum_digits = Σ d_i
Большие степени и вычитание
Выражения из степеней удобно считать в Python: целые числа не переполняются. Но степени вида 10^{10^{12}} физически не вычислить — тогда анализируют структуру записи.
- p^k в основании p — единица и k нулей.
- p^k − 1 в основании p — k цифр p − 1.
- Вычитание из степени превращает нули в p − 1 с заёмом.
- Используйте // вместо /: деление с плавающей точкой теряет точность.
- Для огромных чисел ищите закономерность или считайте по частям.
p^k → 1 и k нулейp^k − 1 → k цифр (p − 1)
Проверка
Перед записью ответа проверьте допустимость цифр, количество разрядов и арифметику.
- Каждая цифра должна быть меньше основания.
- Ведущая цифра не может быть нулём.
- Сверьте количество цифр с границами p^{k−1} ≤ N < p^k.
- Сделайте обратный перевод результата.
- Убедитесь, что ответ требуется в десятичной системе, а не в исходной.