Что проверяет задание

Нужно вычислять значение записи числа в системе счисления, часто с неизвестными цифрами, большой степенью основания или требованием делимости.

Определения

Позиционная система счисления с основанием q: вклад цифры d в позиции k, считая от нуля справа, равен d · q^k.

Цифра, целое от 0 до q − 1. Цифра, не меньшая основания, в этой системе недопустима.

Развёрнутая запись, сумма цифр, умноженных на соответствующие степени основания. Любое «число в системе q» сначала раскрывают так.

Неизвестная цифра, переменная, которая стоит в одной или нескольких позициях. Она пробегает допустимые значения, иногда ещё с запретом ведущего нуля.

Ведущий нуль, нуль в старшей позиции. Для записи числа он обычно запрещён, если речь о самом числе, а не о строке фиксированной длины.

Делимость, значение выражения кратно данному m. Удобно считать весь полином по модулю m, если степени большие.

Длинная арифметика, вычисление, в котором промежуточные степени не помещаются в обычное целое. Тогда либо считают по модулю, либо используют точную арифметику произвольной длины.

Сумма цифр / количество ненулевых цифр, характеристики уже полученной записи в другой системе, а не исходного выражения.

Переход между системами

Чтобы перевести значение в систему q, число делят на q нацело, остатки пишут справа налево. Остаток, очередная младшая цифра.

Если основание само записано выражением, сначала получают десятичное значение всего выражения, затем уже переводят.

Общий алгоритм решения

1. Записать число как многочлен от основания. Каждую неизвестную цифру обозначить переменной с диапазоном.
2. Отбросить варианты, где цифра не меньше основания или где есть ведущий нуль.
3. Если требуется делимость, перейти к сравнению по модулю и упростить степени.
4. Если требуется само значение, вычислить многочлен точно.
5. Если ответ, неизвестная цифра, основание или количество решений, перебрать допустимые значения переменных.
6. Если просят запись результата в другой системе, выполнить перевод и взять из записи то, что спрашивают: последнюю цифру, сумму цифр, количество единиц.

Программа построчно

В задании 14 числа записаны в разных системах счисления. Переводить их вручную долго, а Python делает это одной функцией int. Дальше с числами считают как обычно.

Разберём программу на условии:

Найдите наименьшее целое значение x (0 ≤ x ≤ 7), при котором выражение 2x3₈ + x5₉ равно 221 в десятичной системе. В записи чисел x обозначает одну цифру.

for x in range(0, 8):
    if int(f"2{x}3", 8) + int(f"{x}5", 9) == 221:
        print(x)
        break

for x in range(0, 8): - перебираем все возможные цифры x: 0, 1, …, 7. range(0, 8) не включает 8 - правая граница всегда на единицу больше последнего числа. Подробно - в разделе «Перебор неизвестной цифры».

int(f"2{x}3", 8) - запись числа с цифрой x в середине. f"2{x}3" - f-строка: при x = 5 получится строка "253". int("253", 8) переводит её из восьмеричной системы в десятичное число 171. Подробно - в разделах «f-строка в записи числа» и «Перевод в десятичную: int».

== 221 - проверяем равенство из условия.

print(x) - печатаем подходящую цифру.

break - останавливаем цикл: x перебирается по возрастанию, значит, первое подходящее - наименьшее.

Перевод в десятичную: int

print(int("34", 8))

int(запись, основание) переводит запись числа из системы с указанным основанием в обычное десятичное число:

• запись передаётся строкой в кавычках: "34";
• основание - от 2 до 36;
• int("34", 8) = 3 · 8 + 4 = 28;
• int("B1", 12) = 11 · 12 + 1 = 133: буквы означают цифры больше 9 - A = 10, B = 11, …, Z = 35. Регистр букв не важен: "b1" и "B1" дают одно и то же.

Каждая цифра записи должна быть меньше основания: int("19", 8) вызовет ошибку - в восьмеричной системе нет цифры 9.

После перевода числа складывают, вычитают и умножают обычными знаками +, -, *:

print(int("315", 8) + int("21", 9))

Ответ получается в десятичной системе - так и требует условие.

Перевод из десятичной: функция per

Чтобы записать число в системе с другим основанием, используют функцию из шаблона:

alf = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def per(n, base):
    s = ""
    while n > 0:
        s = alf[n % base] + s
        n = n // base
    return s or "0"

• alf - все цифры по порядку: alf[0] - "0", alf[10] - "A", alf[15] - "F";
• n % base - остаток от деления на основание: это последняя цифра записи;
• alf[n % base] + s - дописываем цифру слева к уже найденным: цифры получаются с конца;
• n = n // base - отбрасываем последнюю цифру (деление нацело);
• цикл повторяется, пока число не станет 0;
• return s or "0" - если число было 0, цикл не выполнится ни разу и s останется пустой строкой; тогда возвращаем "0".

Пример: per(36, 2). 36 % 2 = 0, n = 18 → 18 % 2 = 0, n = 9 → 9 % 2 = 1, n = 4 → 0, n = 2 → 0, n = 1 → 1, n = 0. Цифры с конца: "100100".

Использование:

n = int("B1", 12)
print(per(n, 16))

Сначала переводим запись в обычное число, потом - в нужную систему. Для систем 2, 8 и 16 есть и готовые функции: bin(n), oct(n), hex(n) - но они пишут приставку (0b, 0o, 0x) и маленькие буквы.

Сумма цифр записи

s = "16A"
total = 0
for ch in s:
    total += int(ch, 16)
print(total)

• for ch in s: - перебираем символы записи по одному: "1", "6", "A";
• int(ch, 16) - значение одной цифры: "A" → 10. Для цифр 0-9 подошёл бы и int(ch), но буквы без основания не переводятся;
• total += … - накапливаем сумму: 1 + 6 + 10 = 17.

Перебор неизвестной цифры

Если в записи числа есть неизвестная цифра x, перебирают все её возможные значения:

for x in range(0, 8):
    ...

• границы берут из условия: «0 ≤ x ≤ 7» → range(0, 8);
• если границ нет, x - цифра системы, у которой основание наименьшее из тех, где x встречается: в записи 2x3₈ x ≤ 7.

Для двух неизвестных - два вложенных цикла, они проверяют все пары:

count = 0
for x in range(0, 5):
    for y in range(0, 5):
        if int(f"{x}{y}", 8) + int(f"{y}{x}", 9) == 20:
            count += 1
print(count)

Внешний цикл берёт x = 0 и внутренний перебирает все y, потом x = 1 и снова все y, и так далее: всего 5 · 5 = 25 пар.

Если нужна пара «с наименьшим x, а при равных x - с наименьшим y», подходящие пары собирают в список и берут min:

found = []
...
            found.append((x, y))
x, y = min(found)

min сравнивает пары по первому элементу, а при равенстве - по второму. Это ровно правило из условия.

f-строка в записи числа

int(f"2{x}3", 8)

Буква f перед кавычками делает строку f-строкой: всё, что стоит в фигурных скобках, заменяется значением переменной. При x = 5 строка f"2{x}3" - это "253", при x = 0 - "203".

Так неизвестную цифру подставляют прямо в запись числа, а int(…, 8) переводит получившуюся запись. Несколько неизвестных - несколько пар скобок: f"{x}{y}" при x = 3, y = 1 - это "31".

Если x может быть больше 9 (в системах с основанием больше 10), подставляют не число, а цифру-символ: f"2{alf[x]}3", где alf = "0123456789ABCDEF…".

Длинная арифметика

В большинстве заданий 14 выражение состоит из огромных степеней:

Значение выражения 7 · 512¹²⁰ − 6 · 64¹⁰⁰ + 8²¹⁰ − 255 записали в системе счисления с основанием 8.

В Python целые числа не ограничены по длине, поэтому выражение переписывают как есть и получают точное значение:

n = 7 * 512**120 - 6 * 64**100 + 8**210 - 255

• ** — возведение в степень: 512**120 — это 512¹²⁰;
• * — умножение: «7 · 512¹²⁰» записывается как 7 * 512**120;
• знак «−» в условии — обычный минус -.

Получается число из сотен цифр, но программа считает его за доли секунды. Округления нет: это не float, поэтому все цифры записи будут верными.

Почему степени выбраны «удобными»: 512 = 8³, 64 = 8², значит 512¹²⁰ = 8³⁶⁰ — в восьмеричной записи это единица и 360 нулей. Вручную задачу решают, раскладывая выражение на такие слагаемые и следя за заёмами при вычитании. Программа делает то же самое без рассуждений — достаточно перевести значение в нужную систему и посчитать то, о чём спрашивают.

Цифры записи: цикл с остатком

Чтобы посчитать цифры записи числа в системе с основанием B, строку записи строить не обязательно:

n = 7 * 512**120 - 6 * 64**100 + 8**210 - 255
count = 0
while n > 0:
    if n % 8 == 0:
        count += 1
    n //= 8
print(count)

• n % 8 — остаток от деления на основание: это последняя цифра восьмеричной записи;
• if n % 8 == 0: — проверяем, какая это цифра (здесь — нуль; для цифры 7 было бы == 7);
• n //= 8 — делим нацело: последняя цифра отбрасывается, предпоследняя становится последней;
• цикл идёт, пока число не станет нулём, — так перебираются все цифры справа налево.

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

Единицы в двоичной записи — то же самое при основании 2:

n = 4**16 + 2**34 - 8
count = 0
while n > 0:
    if n % 2 == 1:
        count += 1
    n //= 2
print(count)

Для двоичной системы есть и короткий способ: bin(n).count("1") — функция bin строит запись строкой, а count считает символы.

Характеристики записи

Когда спрашивают не про одну цифру, а про всю запись (сколько разных цифр, сумма, самая длинная серия), удобно сначала получить список цифр:

def digits(n, base):
    res = []
    while n > 0:
        res.append(n % base)
        n //= base
    return res[::-1]

n = 3 * 125**20 + 25**31 - 5**7
d = digits(n, 5)

• res.append(n % base) — добавляем очередную цифру; они получаются с конца записи;
• res[::-1] — разворачиваем список, чтобы цифры шли слева направо, как в записи.

Дальше всё делается одной строкой:

print(len(set(d)))           # сколько различных цифр
print(sum(d))                # сумма цифр
print(len(d))                # сколько разрядов в записи
print(max(range(5), key=d.count))   # какая цифра встречается чаще всего

• set(d) — множество: каждая цифра остаётся один раз;
• key=d.count — max сравнивает цифры по тому, сколько раз они встречаются в списке.

Серия одинаковых цифр подряд — идём по списку и сравниваем соседей:

best = cur = 1
for i in range(1, len(d)):
    if d[i] == d[i - 1]:
        cur += 1
    else:
        cur = 1
    best = max(best, cur)
print(best)

Последние k цифр зависят только от остатка от деления на B^k — переводить всё число не нужно:

print(per(n % 6**4, 6))      # последние 4 цифры шестеричной записи

Так же проверяют, на что оканчивается запись: «оканчивается на 001 в системе b» означает n % b**3 == 1.

Цифры больше 9

В системах с основанием больше 10 цифры от 10 и выше обозначают буквами: A = 10, B = 11, …, Z = 35. Цикл с остатком выдаёт цифру числом, поэтому условия на значения цифр проверяются обычным сравнением:

n = 5 * 1296**597 + 8 * 216**314 - 4 * 36**215 - 54
count = 0
while n > 0:
    x = n % 36
    if x > 9:
        count += 1
    n //= 36
print(count)

• x = n % 36 — значение очередной цифры, от 0 до 35;
• «числовое значение, превышающее 9» — это x > 9, «не превышающее 7» — x <= 7;
• «чётное значение» — x % 2 == 0 (нуль тоже чётный);
• «разряды, которые не являются десятичными цифрами» — это буквы, то есть x >= 10;
• «сколько цифр R и U» — переводим буквы в значения (R = 27, U = 30) и проверяем x in (27, 30).

Сумму цифр с условием считают так же, только вместо счётчика накапливают значения:

total = 0
while n > 0:
    x = n % 31
    if x <= 17:
        total += x
    n //= 31
print(total)

Для оснований больше 36 букв уже не хватает, но цикл с остатком работает с любым основанием — например, с 49.

Перебор x в длинном выражении

Задание вида:

Значение выражения 7¹⁷⁰ + 7¹⁰⁰ − x, где x — целое положительное число, не превышающее 2030, записали в семеричной системе. Определите наибольшее x, при котором в записи ровно 71 нуль.

Перебираем все x и для каждого считаем нули:

for x in range(2030, 0, -1):
    n = 7**170 + 7**100 - x
    count = 0
    while n > 0:
        if n % 7 == 0:
            count += 1
        n //= 7
    if count == 71:
        print(x)
        break

• range(2030, 0, -1) — от 2030 вниз до 1 (ноль не включается): первое подходящее x будет наибольшим, поэтому сразу break;
• для наименьшего x перебирают по возрастанию: range(1, 2031);
• внутри цикла — обычный подсчёт цифр из раздела «Цифры записи: цикл с остатком».

Если спрашивают x, при котором нулей больше всего, храним лучший результат:

best, best_x = -1, 0
for x in range(1, 2031):
    n = 7**170 + 7**100 - x
    count = 0
    while n > 0:
        if n % 7 == 0:
            count += 1
        n //= 7
    if count > best:
        best, best_x = count, x
print(best_x)

• строгое >: при равном количестве нулей остаётся первое найденное, то есть наименьшее x;
• если нужно наибольшее такое x, пишут >= — тогда каждый следующий x с тем же количеством заменяет предыдущий;
• если спрашивают само наибольшее количество нулей, печатают best.

Две тысячи вариантов по несколько сотен цифр — это доли секунды, поэтому рассуждать о заёмах при вычитании не нужно.

Делимость и частное

Задание вида:

123x5₁₅ + 1x233₁₅. Определите наименьшее x, при котором значение выражения кратно 14. Для найденного x вычислите частное от деления на 14.

alf = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

for x in range(15):
    s = int(f"123{alf[x]}5", 15) + int(f"1{alf[x]}233", 15)
    if s % 14 == 0:
        print(s // 14)
        break

• range(15) — все цифры пятнадцатеричной системы: от 0 до 14;
• alf[x] — символ цифры: при x = 12 это "C", поэтому f-строка работает и для «буквенных» цифр;
• s % 14 == 0 — «кратно 14»: остаток от деления равен нулю;
• s // 14 — частное, деление нацело;
• break — x перебираются по возрастанию, значит первое найденное наименьшее.

Варианты вопроса:

• наибольшее x — перебор сверху вниз: range(14, -1, -1);
• ненулевая цифра — range(1, 15);
• значение выражения вместо частного — print(s);
• все x — без break, подходящие x складывают (total += x) или считают (count += 1);
• наименьшее значение выражения, кратное m — храним наименьшее подходящее s.

Почему чаще всего просят кратность p − 1: число в системе с основанием p даёт при делении на p − 1 тот же остаток, что и сумма его цифр. Это можно проверить вручную, но программа надёжнее.

Наименьшее натуральное A, при котором M + A кратно N: у числа M остаток M % N, до следующего кратного не хватает N - M % N. Если остаток нулевой, получится ровно N — это и есть наименьшее натуральное A (нуль натуральным не считается).

a = N - M % N

Основание больше 36

Функция int(запись, основание) работает только для оснований от 2 до 36. Для систем с основанием 37, 40, 47 число записывают списком цифр и переводят сами:

def to10(digits, p):
    n = 0
    for d in digits:
        n = n * p + d
    return n

for x in range(47):
    s = to10([1, x, 2, 4, 10], 47) + to10([x, 2, 0, 2, 4], 47)
    if s % 46 == 0:
        print(s // 46)
        break

• n = n * p + d — схема Горнера: на каждом шаге всё, что уже набрано, сдвигается на один разряд влево (умножение на основание), а справа дописывается новая цифра;
• [1, x, 2, 4, 10] — запись 1x24A₄₇: буква A — это цифра 10, а неизвестная цифра x стоит в списке как переменная;
• x перебирается от 0 до 46 — все цифры 47-ричной системы.

Две неизвестные: выбор пары

Если в записи две неизвестные цифры, перебирают все пары двумя вложенными циклами, а подходящую пару выбирают по правилу из условия.

Наибольшая сумма x + y:

best = -1
for x in range(16):
    for y in range(16):
        s = int(f"27A{alf[x]}23", 16) + int(f"8{alf[y]}E5D2", 16)
        if s % 5 == 0:
            best = max(best, x + y)
print(best)

Частное для пары с наибольшей суммой, при равной сумме — с наибольшим x. Кортежи в Python сравниваются по первому элементу, при равенстве — по второму, поэтому правило записывается ключом (x + y, x):

best = None
for x in range(14):
    for y in range(14):
        s = int(f"14{alf[y]}5{alf[x]}2", 14) + int(f"31{alf[x]}2{alf[y]}3", 14)
        if s % 9 == 0:
            key = (x + y, x)
            if best is None or key > best[0]:
                best = (key, s)
print(best[1] // 9)

• best = None — пока ничего не найдено;
• best = (key, s) — храним вместе с ключом и значение выражения: оно нужно для ответа.

Наименьшее значение выражения, кратное m:

best = None
for x in range(9):
    for y in range(9):
        s = int(f"88{x}4{y}", 9) + int(f"7{x}44{y}", 11)
        if s % 61 == 0 and (best is None or s < best):
            best = s
print(best // 61)

Цифра x должна быть допустима во всех системах, где встречается: если x стоит в числах с основаниями 9 и 11, то x ≤ 8.

Сколько различных значений принимает сумма — подходящие суммы складывают в множество, оно хранит каждое значение один раз:

sums = set()
...
            sums.add(x + y)
print(len(sums))

Неизвестное основание

Если основание неизвестно, перебирают его. Наименьшее возможное основание — на единицу больше наибольшей цифры записи: в числе AB267D1 есть цифра D = 13, значит p ≥ 14.

for p in range(14, 37):
    s = int("AB267D1", p) + int("F024A89", p)
    if s % (p - 1) == 0:
        print(p)
        break

• range(14, 37) — от наименьшего допустимого основания до 36 (дальше int не работает);
• основание в int — переменная p, запись числа при этом не меняется;
• s % (p - 1) — делитель зависит от основания, поэтому скобки обязательны.

Если основание нужно наибольшее — перебор сверху вниз: range(36, 13, -1).

Если про основание сказано только, что значение делится на какое-то число, печатаем результат для всех подходящих оснований — в правильно составленном задании строка будет одна:

for a in range(28, 37):
    s = int("KXRB", a) + int("LMN", a) - int("PQ", a)
    if s % 1747 == 0:
        print(s // 1747)

Неизвестное основание и неизвестную цифру одновременно перебирают двумя циклами: внешний — основание, внутренний — цифра от 0 до основания минус один.

for y in range(7, 37):
    for x in range(y):
        if int(f"4163{alf[x]}1", y) == 247393:
            print(f"{x}{y}")

Буквы-цифры: перебор product

Задание вида:

В системе счисления с основанием p выполняется равенство zxyx4 + xy658 = wzx73. Определите число xyzw_p.

Неизвестных цифр несколько, и все они — цифры одной и той же системы p. Все наборы цифр перебирает функция product:

from itertools import product

alf = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

for p in range(9, 17):
    for x, y, z, w in product(alf[:p], repeat=4):
        if int(f"{z}{x}{y}{x}4", p) + int(f"{x}{y}658", p) == int(f"{w}{z}{x}73", p):
            print(int(x + y + z + w, p))

• range(9, 17) — в записи есть цифра 8, значит p ≥ 9; верхняя граница берётся из условия;
• alf[:p] — строка всех цифр системы p: при p = 12 это "0123456789AB";
• product(alf[:p], repeat=4) — все наборы из четырёх цифр: (0, 0, 0, 0), (0, 0, 0, 1), … — ровно p⁴ вариантов;
• x, y, z, w здесь символы, поэтому их можно сразу подставлять в f-строку;
• x + y + z + w — склейка символов в запись числа xyzw, которую переводит int(…, p).

break здесь не ставят: если равенство подходит единственному набору, программа напечатает одну строку. Несколько строк — повод перечитать условие.

Запись числа: начало, конец, длина

Когда нужно проверить, как выглядит запись числа, удобнее всего получить её строкой функцией per:

alf = "0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ"

def per(n, base):
    s = ""
    while n > 0:
        s = alf[n % base] + s
        n //= base
    return s or "0"

count = 0
for n in range(1, 1001):
    s = per(n, 20)
    if len(s) == 3 and s[0] == "1" and s[-1] == "J":
        count += 1
print(count)

• len(s) == 3 — запись трёхзначная;
• s[0] — первый символ записи, s[-1] — последний;
• s.startswith("12") и s.endswith("21") — запись начинается (оканчивается) на несколько символов сразу;
• условия про две разные системы проверяют одновременно: per(n, 3).endswith("21") and per(n, 5).startswith("3").

Если нужно перечислить найденные числа слитно в порядке убывания:

print("".join(str(n) for n in sorted(found, reverse=True)))

Обратная задача — по числу найти основания. Перебираем основания и смотрим на запись:

total = 0
for p in range(2, 37):
    s = per(28, p)
    if s.endswith("3") and len(s) > 1:
        total += p
print(total)

Простые числа и квадраты

Проверка числа на простоту — делители ищем от 2 до корня из числа:

def prime(n):
    if n < 2:
        return False
    for d in range(2, int(n ** 0.5) + 1):
        if n % d == 0:
            return False
    return True

• числа меньше 2 (в том числе 0, 1 и отрицательные) простыми не считаются;
• если у числа есть делитель, больший корня, то есть и парный ему — меньший корня, поэтому дальше корня искать не нужно.

Полный квадрат — корень из числа целый:

if int(r ** 0.5) ** 2 == r:
    ...

Для больших чисел надёжнее math.isqrt(r) ** 2 == r — функция isqrt считает целый корень без ошибок округления.