14 задание ЕГЭ информатика

Задание 14 – значение выражения со степенями записывают в системе с основанием b; нужно посчитать цифры с условием. Или найти неизвестную цифру x в записях чисел в разных системах, чтобы выполнялось равенство или делимость. 1 балл. Python работает с большими числами точно.

Перевод в систему с основанием b

def to_base(x, b):
    d = []
    while x > 0:
        d.append(x % b)
        x //= b
    return d[::-1]           # список цифр (числовых значений)

x = 4**20 + 2**30 - 16
print(bin(x).count("1"))     # единицы в двоичной записи: 27
digits = to_base(x, 27)
print(sum(1 for c in digits if c > 9))

Цифры больших систем удобнее хранить числами, а не буквами – сравнивать проще.

Неизвестная цифра x

for x in range(15):          # x – цифра системы с основанием 15
    a = int(f"97{x:X}68", 15) # f-строка подставит цифру (A..E для 10..14)
    b = int(f"7{x:X}233", 15)
    if (a + b) % 13 == 0:
        print(x, (a + b) // 13)    # x = 11 (цифра B)
        break

int(строка, основание) работает для оснований до 36.

Разобранный пример (устно). Сколько единиц в двоичной записи 4²⁰ + 2³⁰ − 16? 4²⁰ = 2⁴⁰ – одна единица. 2³⁰ − 2⁴ = 2²⁹ + … + 2⁴ – 26 единиц. Итого 27.

Правило: $b^n-b^m$ (n > m) в системе с основанием b – это (n − m) цифр «b − 1», за ними m нулей.

Ловушки: «цифры со значением больше 9» – это A, B, … (10, 11, …); в задачах с x цифра x должна быть меньше основания каждой системы, где она встречается; не перепутай // и /.