Значение выражения: `(64^25+4^10)-(16^20+32^3)` записали в системе счисления с основанием `A`. Напишите программу, которая определяет в каком разряде такой записи числа при…

Задача просит определить, в каком разряде числа в системе счисления с основанием 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 = (6425 + 410) - (1620 + 323), а затем ищет первый разряд справа, равный 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.