Задача просит определить, в каком разряде числа в системе счисления с основанием A, считая разряды справа налево начиная с нуля, впервые встречается цифра B. Условие: 1 < A < 10, B < A.
1) Математическая подготовка
- Выразим каждое число через степени двойки:
- 64^25 = (2^6)^25 = 2^150
- 4^10 = (2^2)^10 = 2^20
- 16^20 = (2^4)^20 = 2^80
- 32^3 = (2^5)^3 = 2^15
- Тогда N = (64^25 + 4^10) − (16^20 + 32^3) = 2^150 + 2^20 − 2^80 − 2^15.
- Заметим, что N делится на 2^15, потому что в выражении выделяется множитель 2^15: N = 2^15 * M, где M = 2^135 + 2^5 − 2^65 − 1. И M нечетно, следовательно v2(N) = 15 (N имеет ровно 15 нулей в двоичной записи).
2) Как найти нужный разряд
- Мы ищем минимальный k ≥ 0 такой, что цифра k-го разряда числа N в системе исчисления основанием A равна B.
- Формально: цифра k равна (N // A^k) mod A. Нужно найти наименьшее k, при котором эта величина равна B.
- Реализация на практике: поразрядно делить число N на A, вычислять остаток от деления N % A на каждом шаге. Первый разряд, равный B, даст искомный k.
3) Алгоритм
- Вычислить N точно (это удобно в языках с big-int, например Python).
- Установить k = 0.
- Пока N > 0:
- если N % A == B, вернуть k
- иначе N = N // A, k += 1
- Если цикл завершится без нахождения B (редко для заданного числа), вернуть признак отсутствия (например -1).
4) Пример кода на Python
- Учитывая, что A и B считываются из входа как две целые числа (через пробел).
Пример программы (Python):
- Программа reads A и B, вычисляет N = (64**25 + 4**10) - (16**20 + 32**3), а затем ищет первый разряд справа, равный B.
Пример кода:
import sys
def main():
data = sys.stdin.read().strip().split()
if len(data) < 2:
return
A = int(data[0])
B = int(data[1])
# Точное вычисление N
N = (64**25 + 4**10) - (16**20 + 32**3)
k = 0
while N > 0:
if N % A == B:
print(k)
return
N //= A
k += 1
# В теории могло бы быть отсутствие цифры B, но это не должно происходить для данной задачи.
print(-1)
if __name__ == "__main__":
main()
5) Что дает этот подход
- Простота реализации и ясность: можно легко проверить для любых допустимых A (2..9) и B < A.
- Надежность за счет использования больших целых чисел (Python справляется с такими величинами без проблем).
- Временная сложность пропорциональна числу digits в системе основанием A, то есть примерно O(log_A N). Для данного N это очень маленькое число.
6) Дополнительные заметки
- Ваша задача выполняется корректно, потому что N явно задано и фиксировано: N = 2^150 + 2^20 − 2^80 − 2^15, а программа работает для любых допустимых A и B.
- Если по каким-то причинам требуется реализация на другом языке без big-int, можно реализовать с помощью модульной арифметики и вычислять N мод A^t пошагово, но это уже усложняет код. В Python решение выше идеальное по простоте и читабельности.
Если хотите, могу адаптировать код под другой язык (C++, Java, etc.) или добавить обработку случая, когда цифра B не встречается вRepresentation.
