No.044 D

$n$ を $b$ 進数で表したときの各桁の値を $a_i$ とすると,

$$n = a_0 b^0 + a_1 b^1 + a_2 b^2 + a_3 b^3 + \dots \\ s = a_0 + a_1 + a_2 + a_3 + \dots$$

となる. ここから,

$$\begin{align} n &= a_0 + a_1 + a_2 + \dots + a_1 (b-1) + a_2 (b^2-1) + a_3 (b^3-1) + \dots \\ &= s + a_1 (b-1) + a_2 (b^2-1) + a_3 (b^3-1) + \dots \end{align}$$

となり,

$$n-s = a_1 (b-1) + a_2 (b^2-1) + a_3 (b^3-1) + \dots$$

となる.

まず, $n \lt s$ とはなりえないことがわかるので, そのような場合は $-1$ を出力する.

次に, $n = s$ のときは $a_1 = a_2 = \dots = 0$ であるので, $b = n+1$ が最小の $b$ である.

$n \gt s$ のときであるが, $b^k-1$ は $b-1$ で割り切れるため, $n-s$ も $b-1$ の倍数となる.

よって, $n-s$ の約数を $p_i$ とすると, $b = p_i + 1$ として $n$ から $s$ が求められるか確認すればいい.