← 返回题目列表

AtCoder · arc060_b

D. 数字和

中文机器翻译题面 查看原题

分数: 500 点

问题陈述

对于整数 b (b \geq 2) 和 n (n \geq 1),让函数 f(b,n) 定义如下:

  • f(b,n) = n,当 n < b
  • f(b,n) = f(b,\,{\rm floor}(n / b)) + (n \ {\rm mod} \ b),当 n \geq b

在这里, {\rm floor}(n / b) 表示不超过的最大整数 n / b, 和 n \ {\rm 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 \geq 2) 这样 f(b,n)=s。 如果答案是肯定的,还找到最小的这样的 b.

约束

  • 1 \leq n \leq 10^{11}
  • 1 \leq s \leq 10^{11}
  • n,\,s 是整数。

输入

输入由标准输入按以下格式给出:

n
s

输出

如果存在整数 b (b \geq 2) 这样 f(b,n)=s,打印最小的这样 b。 如果这样的话 b 不存在,打印 相反, -1 。


示例输入 1

87654
30

示例输出 1

10

示例输入 2

87654
138

示例输出 2

100

示例输入 3

87654
45678

示例输出 3

-1

示例输入 4

31415926535
1

示例输出 4

31415926535

示例输入 5

1
31415926535

示例输出 5

-1