10633. На редкость простая задача

N – некоторое целое число, имеющее в десятичной записи хотя бы две цифры. Джон производит над этим числом следующую операцию: он зачеркивает последнюю цифру, получает число M и вычисляет N – M. Зная значение N – M, следует найти N.

Вход. Каждая строка содержит целое положительное число, являющееся значением N – M (10 £ N – M £ 10¹⁸). Последняя строка содержит 0 и не обрабатывается.

Выход. Для каждого входного значения N – M вывести все возможные N в возрастающем порядке. Числа в одной строке следует разделять одним пробелом.

Пример входа

18

0

Пример выхода

19 20

РЕШЕНИЕ

математика

Анализ алгоритма

Пусть N = 10 * X + a, где а – последняя цифра числа N (0 £ a £ 9). Тогда M = X, N – M = 10 * X + a – X = 9 * X + a. Обозначим n = N – M. Тогда a = n mod 9, X = (n – a) / 9. Очевидно, что искомым будет N = 10 * X + a = 10 * (n – a) / 9 + n mod 9.

Если a = n mod 9 = 0, то последняя цифра a может равняться 9, так как 9 mod 9 = 0. Тогда X = (n – 9) / 9 = n / 9 – 1, откуда N = 10 * X + a = 10 * (n / 9 + 1) + 9.

Таким образом если значение N – M делится на 9, то существует два разных значения N. Иначе – одно.

Пример

Если N = 19, то M = 1 и N – M = 18. При N = 20 получим M = 2 и N – M = 18. Если N – M = 18 (делится на 9), то существует два разных значения N: 19 и 20.

Реализация алгоритма

Объявим переменные a, n, x типа long long.

long long a, n, x;

Вводим n = N – M. Последовательно вычисляем значения a, x и выводим результат согласно приведенному выше анализу.

while(scanf("%lld",&n), n)

{

a = n % 9;

x = (n - a) / 9;

if (!a) printf("%lld ",10 * (x - 1) + 9);

printf("%lld\n",10 * x + a);

}