Atcoder ARC060D Digit Sum
看到 \(n\le 10^{11}\)，考虑按根号分为两部分处理。
对于 \(b\le \sqrt{n}\)，考虑直接暴力算 \(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\) 再去检验 \(f(b, n)\) 的值是否为 \(s\)，容易得到这部分的时间复杂度也是 \(O(\sqrt{n})\) 的。
除此之外还有个情况 \(b > n\)，这个时候 \(f(b, n) = n\)，判掉就行。
综上，时间复杂度为 \(O(\sqrt{n})\)。