Задание 14 КЕГЭ: число в системе с основанием N оканчивается на определённую цифру — как решать?
Задание 14: дано число вида (формула с основанием системы, например 7^n + что-то) и надо найти, при каком условии его запись в этой системе оканчивается на конкретную цифру или сумма цифр равна чему-то. Руками в системах счисления путаюсь страшно. Можно это перебором на питоне?
2 ответа
Да, и это самый надёжный способ. Тебе нужны две вещи: посчитать значение и перевести его в нужную систему.
Перевод числа в систему с основанием b:
def to_base(n, b):
if n == 0:
return '0'
s = ''
while n > 0:
s = str(n % b) + s # для b<=10; для b>10 нужны буквы
n //= b
return s
Теперь перебираешь по условию задачи. Например, "при каком наименьшем натуральном n сумма цифр числа 7**n + k в семеричной системе равна 5":
for n in range(1, 1000):
val = 7 ** n + 5
s = to_base(val, 7)
if sum(int(c) for c in s) == 5:
print(n)
break
"Оканчивается на цифру d" — это просто s[-1] == 'd' (последний символ записи) или, что то же, val % b == d. Перебор + перевод закрывает почти любую формулировку задания 14.
Маленькое, но важное: остаток val % b — это последняя цифра записи в системе b. Поэтому "оканчивается на цифру d в системе b" часто решается вообще без перевода: условие val % b == d. А "сумма последних двух цифр" → val % (b*b), дальше разбираешь на две цифры. Иногда так даже руками быстрее, чем кодом. Но если запутался — переводи функцией выше и считай по символам.