ABC044 D - 桁和 / Digit Sum (500点)

2020年2月16日

問題

$n$,$s$に対して以下の変形ができます。

$n = a_0b^0 + a_1b^1 + ... + a_mb^m$

$s = a_0 + a_1 + ... + a_m$

$b$が大きくなるほど$m$は小さくなります。なぜなら$m$は$n$を$b$で何回割れるかみたいなことを表す値だからです。

$m = floor(\log_b n)$

$b$と$m$の関係を追ってみます。

$2 \leq b \leq \sqrt{n}$のとき、$O(\sqrt{n})$で$b$を全探索すれば良いです。

以降、$b > \sqrt{n}$の場合を考えます。このとき、

とかけます。$(1)$式から、$n = a_0 + a_1b \geq a_1b > a_1 \sqrt{n}$より、$\sqrt{n} > a_1$を得ます。

また、$(1, 2)$式から、$b = (n - s) / a_1 + 1$です。

よって、$\sqrt{n} > a_1 \geq 1$となる$a_1$を全探索すれば$b$が求まります。

ちなみに、$s > n$を満たす$b$は無く、$s = n$を満たす$b$は$n+1$です。

割り算が出たら$\sqrt{n}$を考えるというのは典型っぽい？今回の場合だと$b$を$\sqrt{n}$で場合分けすることによって探索が$O(\sqrt{n})$でできるようになりました。頭いい。