https://atcoder.jp/contests/abc044/tasks/arc060_b
n,sに対して以下の変形ができます。
n=a0b0+a1b1+...+ambm
s=a0+a1+...+am
bが大きくなるほどmは小さくなります。
なぜならmはnをbで何回割れるかみたいなことを表す値だからです。
m=floor(logbn)
bとmの関係を追ってみます。
- b≤nのとき、m≥2
- b>nのとき、m<2
2≤b≤nのとき、O(n)でbを全探索すれば良いです。
以降、b>nの場合を考えます。このとき、
n=a0+a1b...(1)s=a0+a1...(2)
とかけます。(1)式から、n=a0+a1b≥a1b>a1nより、n>a1を得ます。
また、(1,2)式から、b=(n−s)/a1+1です。
よって、n>a1≥1となるa1を全探索すればbが求まります。
ちなみに、s>nを満たすbは無く、s=nを満たすbはn+1です。
submission(Ruby)
割り算が出たらnを考えるというのは典型っぽい?
今回の場合だとbをnで場合分けすることによって探索がO(n)でできるようになりました。頭いい。
- editorial.pdf
- ARC060_D - 桁和 / Digit Sum - seica_atの日記