Задание 14: Кодирование чисел. Системы счисления

Типичная формулировка: даны два числа, записанные в системах счисления с разными основаниями, где часть цифр заменена буквами x и y. Нужно найти такие значения x и y (допустимые цифры в соответствующих системах), при которых сумма чисел минимальна и кратна заданному числу m. Затем вычисляется частное от деления суммы на m, и это частное записывается в ответе в десятичной системе. Задание оценивается в 1 балл, ответ — короткая числовая строка без указания основания.

• Позиционная запись числа: $N_b=a_{k-1}b^{k-1}+a_{k-2}b^{k-2}+\dots+a_1b^1+a_0b^0$
• Допустимые цифры в системе с основанием $b$: $0 \le a_i \le b-1$
• Перевод из десятичной в систему с основанием $b$: последовательное деление с остатком
• Свойство модульной арифметики: $(A+B)\bmod m = \left((A\bmod m)+(B\bmod m)\right)\bmod m$
• Линейное сравнение: $ax \equiv c \pmod m$ решается через обратный элемент, если $\gcd(a,m)=1$
• Обратный элемент по модулю: $a \cdot a^{-1}\equiv 1 \pmod m$, находится расширенным алгоритмом Евклида
• Правило переноса при сложении столбиком в системе с основанием $b$: если сумма цифр разряда $\ge b$, вычитаем $b$ и переносим 1 в следующий разряд

1. Определить основания систем счисления обоих чисел и диапазоны допустимых цифр для x и y в каждой системе; взять пересечение диапазонов, если переменная встречается в обоих числах.
2. Записать каждое число как линейную функцию от x и y: $A=A_0+P_1x+Q_1y$, $B=B_0+P_2x+Q_2y$.
3. Сложить выражения и привести к виду $S=S_0+Px+Qy$.
4. Найти остатки $S_0\bmod m$, $P\bmod m$, $Q\bmod m$, где $m$ — заданное число кратности.
5. Составить сравнение $Px+Qy\equiv -S_0 \pmod m$.
6. Перебирать x, начиная с минимального допустимого значения; для каждого x решить сравнение относительно y через обратный элемент по модулю и проверить, что найденное y попадает в допустимый диапазон.
7. Как только найдена первая подходящая пара (минимальный x, минимальный подходящий y), это и есть искомое решение — сумма минимальна. …