AT_arc060_b [ABC044D] 桁和

题目描述

对于 $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

输入 #1

87654
30

输出 #1

10

输入输出样例 #2

输入 #2

87654
138

输出 #2

100

输入输出样例 #3

输入 #3

87654
45678

输出 #3

-1

输入输出样例 #4

输入 #4

31415926535
1

输出 #4

31415926535

输入输出样例 #5

输入 #5

1
31415926535

输出 #5

-1

说明/提示

限制条件

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

由 ChatGPT 4.1 翻译