Олимпиадный тренинг

Задача . Сумма цифр числа


Для целых чисел b ( b >= 2 ) и n ( n >= 1 ) пусть функция f(b, n) определяется следующим образом:
\(f (b, n) = n, когда\ n < b \\ f (b, n) = f (b, floor (n / b)) + (n \ mod \ b), когда \ n >= b\)

Здесь
floor(n / b) обозначает наибольшее целое число, не превышающее n / b;
n mod b обозначает остаток от n, деленный на b.

Менее формально f(b, n) равно сумме цифр n, записанных в базе b. Например, справедливо следующее:
\(f (10,87654) = 8 + 7 + 6 + 5 + 4 = 30\\ f (100,87654) = 8 + 76 + 54 = 138\)

Вам даны целые числа n и s. Определите, существует ли целое число b (b >= 2) такое, что f(b, n) = s. Если ответ положительный, найдите наименьшее из таких b.


Входные данные
В первой строке вводится целое число n (1 <= n <= 1011). Во второй строке - целое число (1 <= s <= 1011).

Выходные данные
Выведите ответ на задачу. Если ответа нет, то выведите -1.
 

 

Примеры
Входные данные Выходные данные
1 87654
30
10
2 87654
138
100
3 87654
45678
-1
4 31415926535
1
31415926535
5 1
31415926535
-1

 




time 1000 ms
memory 256 Mb
Правила оформления программ и список ошибок при автоматической проверке задач

Статистика успешных решений по компиляторам
 Кол-во
С++ Mingw-w646
Комментарий учителя