/ 
Time Limit: 2 sec / Memory Limit: 256 MB
配点 : 500 点
問題文
2 以上の整数 b および 1 以上の整数 n に対し、関数 f(b,n) を次のように定義します。
- n < b のとき f(b,n) = n
- n \geq b のとき f(b,n) = f(b,\,{\rm floor}(n / b)) + (n \ {\rm mod} \ 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 が与えられます。 f(b,n)=s を満たすような 2 以上の整数 b が存在するか判定してください。 さらに、そのような b が存在するならば、その最小値を求めてください。
制約
- 1 \leq n \leq 10^{11}
- 1 \leq s \leq 10^{11}
- n,\,s はいずれも整数である
入力
入力は以下の形式で標準入力から与えられる。
n s
出力
f(b,n)=s を満たす 2 以上の整数 b が存在するならば、そのような 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
Score : 500 points
Problem Statement
For integers b (b \geq 2) and n (n \geq 1), let the function f(b,n) be defined as follows:
- f(b,n) = n, when n < b
- f(b,n) = f(b,\,{\rm floor}(n / b)) + (n \ {\rm mod} \ b), when n \geq b
Here, {\rm floor}(n / b) denotes the largest integer not exceeding n / b, and n \ {\rm mod} \ b denotes the remainder of n divided by b.
Less formally, f(b,n) is equal to the sum of the digits of n written in base b. For example, the following hold:
- f(10,\,87654)=8+7+6+5+4=30
- f(100,\,87654)=8+76+54=138
You are given integers n and s. Determine if there exists an integer b (b \geq 2) such that f(b,n)=s. If the answer is positive, also find the smallest such b.
Constraints
- 1 \leq n \leq 10^{11}
- 1 \leq s \leq 10^{11}
- n,\,s are integers.
Input
The input is given from Standard Input in the following format:
n s
Output
If there exists an integer b (b \geq 2) such that f(b,n)=s, print the smallest such b.
If such b does not exist, print -1 instead.
Sample Input 1
87654 30
Sample Output 1
10
Sample Input 2
87654 138
Sample Output 2
100
Sample Input 3
87654 45678
Sample Output 3
-1
Sample Input 4
31415926535 1
Sample Output 4
31415926535
Sample Input 5
1 31415926535
Sample Output 5
-1