Неизвестная цифра и кратность

Признак делимости на девять работает в любой системе

Десятичное число делится на 9, если сумма его цифр делится на 9. Причина простая: десятка при делении на девять даёт остаток 1, поэтому каждый разряд по остатку равен своей цифре.

С основанием p всё так же, только вместо девятки стоит p − 1.

Кратность p − 1 — это сумма цифр.

Как искать неизвестную цифру

Складываем цифры всех операндов, вместо неизвестной пишем x. Выходит выражение вида S + m · x, где m — сколько раз x встретился.

Ищем такие x от 0 до p − 1, при которых S + m · x делится на p − 1. Подходящих значений обычно несколько, и идут они с постоянным шагом.

Из них берём то, которое просят: наибольшее или наименьшее.

В ответ идёт не x, а частное. Его считает программа: собирает число по схеме «умножили на p, прибавили цифру» и делит сумму.

Пример

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

Здесь p − 1 = 14, значит смотрим на сумму цифр.

Первое число даёт 1 + 2 + 3 + x + 5, второе — 1 + x + 2 + 3 + 3. Вместе получается 20 + 2x.

Перебираем x от 0 до 14: на 14 делится при x = 4 и при x = 11.

Наименьшее x равно 4, остаётся поделить сумму на 14.


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

Что печатает программа

4 8767
11 10462

Подходят два значения. Просили наименьшее — берём строку с x = 4, в ответ идёт 8767.

Проверь себя

Ловушки

• Проверяли делимость на p вместо p − 1.
• Учли x один раз, хотя он встречается в нескольких операндах.
• Записали в ответ x, а не частное.
• Нашли одно подходящее x и остановились, не проверив остальные.
• Собрали число, приписав цифру к строке десятичной записи.