看到 \(n\le 10^{11}\)，考虑按根号分为两部分处理。
对于 \(b\le \sqrt{n}\)，考虑直接暴力算 \(\operatorname{f}(b, n)\) 判断是否等于 \(s\)，这部分的计算量是 \(O(\sqrt{n})\) 级别的。
对于 \(\sqrt{n} < b \le n\)，则这个时候在 \(b\) 进制下 \(n\) 也只有两位，考虑列出 \(n, s\) 与 \(n\) 在 \(b\) 进制下的数 \(\overline{xy}\) 的关系：
\(\begin{cases}n = bx + y\\ s = x + y\end{cases}\)
于是就有 \(n - s = (b - 1)\times x\)，考虑枚举 \(n - s\) 的因数得到 \(b - 1\) 再去检验 \(\operatorname{f}(b, n)\) 的值是否为 \(s\)，容易得到这部分的时间复杂度也是 \(O(\sqrt{n})\) 的。
除此之外还有个情况 \(b > n\)，这个时候 \(\operatorname{f}(b, n) = n\)，判掉就行。
综上，时间复杂度为 \(O(\sqrt{n})\)。
// lhzawa(https://www.cnblogs.com/lhzawa/)
// Problem: D - Digit Sum
// Contest: AtCoder - AtCoder Regular Contest 060
// URL: https://atcoder.jp/contests/arc060/tasks/arc060_b
// Memory Limit: 256 MB
// Time Limit: 2000 ms
//
// Powered by CP Editor (https://cpeditor.org)
#include<bits/stdc++.h>
using ll = long long;
ll f(ll n, ll b) {
return n % b + (n >= b ? f(n / b, b) : 0);
}
int main() {
ll n, s;
scanf("%lld%lld", &n, &s);
if (n == s) {
printf("%lld\n", n + 1);
return 0;
}
ll w = 2;
for (; w * w <= n; w++) {
if (f(n, w) == s) {
printf("%lld\n", w);
return 0;
}
}
ll ans = -1;
for (ll i = 1; i * i <= n - s; i++) {
if ((n - s) % i == 0 && f(n, (n - s) / i + 1) == s) {
ans = (n - s) / i + 1;
}
}
printf("%lld\n", ans);
return 0;
}