题目描述

对于大于等于 $2$ 的整数 $b$ 以及大于等于 $1$ 的整数 $n$，定义函数 $f(b,n)$ 如下：

• 当 $n < b$ 时，$f(b,n) = n$；
• 当 $n \geq b$ 时，$f(b,n) = f(b,\,\mathrm{floor}(n / b)) + (n \bmod b)$。

这里，$\mathrm{floor}(n / b)$ 表示不超过 $n / b$ 的最大整数，$n \bmod 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$。请判断是否存在大于等于 $2$ 的整数 $b$ 使得 $f(b,n) = s$。如果存在，请求出满足条件的最小 $b$。

输入格式

输入以如下格式从标准输入读入：

$n$ $s$

输出格式

如果存在大于等于 $2$ 的整数 $b$ 满足 $f(b,n) = s$，请输出最小的这样的 $b$。如果不存在，请输出 -1。

样例 1

输入

87654
30

输出

10

样例 2

输入

87654
138

输出

100

样例 3

输入

87654
45678

输出

-1

样例 4

输入

31415926535
1

输出

31415926535

样例 5

输入

1
31415926535

输出

-1

说明/提示

限制条件

• $1 \leq n \leq 10^{11}$
• $1 \leq s \leq 10^{11}$
• $n,\,s$ 均为整数。

由 ChatGPT 4.1 翻译