ARC #060 D
\(s\) は \(b\) 進数で表したときの各桁の和であるので,
\[n = a_0 + a_1b + a_2b^2 + a_3b^3 + \dots\]とすると,
\[s = a_0 + a_1 + a_2 + a_3 + \dots\]となる. よって,
\[n-s = a_1(b-1) + a_2(b^2-1) + a_3(b^3-1) + \dots\]となる. \(b^k-1\) は \(b-1\) で割り切れるので, \(n-s\) は \(b-1\) で割り切れる必要がある.
\(b\) が決まれば \(n\) から \(s\) は求められる.
\(n-s\) の約数の個数は多くとも \(2\sqrt{n-s}\) で収まるので, 全探索で計算可能である.