問題

D - 桁和 / Digit Sum

考察

nn,ssに対して以下の変形ができます。

n=a0b0+a1b1+...+ambmn = a_0b^0 + a_1b^1 + ... + a_mb^m

s=a0+a1+...+ams = a_0 + a_1 + ... + a_m

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

m=floor(logbn)m = floor(\log_b n)

bbmmの関係を追ってみます。

  • bnb \leq \sqrt{n}のとき、m2m \geq 2
  • b>nb > \sqrt{n}のとき、m<2m < 2

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

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

n=a0+a1b...(1)s=a0+a1...(2)\begin{array}{c} n = a_0 + a_1b \, ...(1)\\ s = a_0 + a_1 \, ...(2) \end{array}

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

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

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

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

submission(Ruby)

学び

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

参考

  1. editorial.pdf
  2. ARC060_D - 桁和 / Digit Sum - seica_atの日記