https://emtubasa.hateblo.jp/entry/2018/11/02/000000

問題
 提出コード
これが500点？という感じの難易度でした。苦手意識があり、全く違うベクトルの考察を始めてしまうので解ける気がしません…

解法

$n \lt b$ のとき、 $s=n$ になります。それ以外で $s=n$ になるような $b$ は存在しません。ということで、 $s=n$ の場合は、 $b=n+1$ が答えになります。この場合のみ、先に処理をします。
$O(\sqrt{n})$ が間に合うので、どうにかして $\sqrt{n}$ か $logn$ ぐらいに計算量を落としたいです。
$b$ 進数について考えるとき、 $\sqrt{n}$ までは $b$ 進数になおすと3桁以上ですが、それより大きい数字(ただし $n$ 以下です)をなおすと2桁になります。
ということで、 $b$ が $\sqrt{n}$ におさまるパターンと、そうでないパターンで場合分けをしていき考えます。

$b$ が $\sqrt{n}$ におさまるパターン
$O(\sqrt{n})$ が間に合うため、全探索ができそうです。
桁和の計算もそこまで時間がかかりません(logにおさまります)。ということで、2から順番に調べていき、条件を満たす $b$ が見つかった時点でうちきります。
$b$ が $\sqrt{n}$ におさまらないパターン
先ほど、こちらのパターンは $b$ 進数に直すと2桁となる、と言いました。
2桁の数字を、"pq"と表現することにすると、 $b$ 進数の定義から、
$n = p×b + q$
という条件が成り立ちます。
また、問題の条件から、
$s = p + q$ を満たすようにしなければなりません。ということで、 $p,q$ についての方程式が2つできたので、これを連立します。上の式から、下の式を引くことで、
$n-s = p(b-1)$
という条件式になります。" $b =$ "の形に直すと、
$b = \frac{n-s}{p} + 1$
となります。
あとは、細かい条件をすべて満たしつつ、この方程式も満たすような $b$ の中で、最も小さいものを求めれば完了です。
$p$ について探索すればいいのですが、 $s$ 通り試していたのでは間に合いませんので、 $\frac{n-s}{p}$ が割り切れたときに、 $p = \frac{n-s}{p}$ とおきなおして同時に調べれば、 $O(\sqrt{n-s} )$ で事足ります。
あとは、
$b \geqq q$ 、つまり $b \geqq s-p$
$b^{2} > n$ (これは、 $b$ が $\sqrt{n}$ におさまらないということを表しています)
$n-s\geqq 0$
等の条件を加えて、全て満たすような場合の $b$ の最小値を求めれば、答えになります。