ARC060_D - 桁和 / Digit Sum

考察

制約の10^{11}がちょっと気になる。
最小の数字と言われているので、基本全部見たくなる。
数字に関してわちゃわちゃする問題なので、まず式に表すべきであろう。

n = a_{0}b^{0} + a_{1}b^{1} + ... + a_{n}b^{n}
a_{1} + a_{2} + ... + a_{n} = s

という感じかな?
これをどうにらめっこするべきか、とりあえずいろいろ数字を入れてみる。この時に割り算とか出てきているので頭の中に\sqrt{n}があってもいいかも。
b = 2の時は大きくてもざっくりn = 37とかになるのかなとか、
当然数字が大きくなるにつれてnは小さくなる。
ある程度大きくなると(\sqrt{n}から)

n = a_{0}b^{0} + a_{1}b^{1}
a_{0} + a_{1} = s

になることがわかる、ここで場合分けをするとよさそうということになる。
{b} \geq {\sqrt{n}}なのでa_{1} \leq {\sqrt{n}}はわかるためこれで走査すりゃいいんじゃないという感じに。
この時にbの値が一意になることを確認することは大事。
まあ、割り算が出てきたりしたら\sqrt{n}がいい場合分けになりそうみたいな認識あってもいいかもね。

という、tex記法練習回でした。