AtCoder Beginner Contest 233 E 問題 Σ[k=0..10^100]floor(X／10^k)

$\displaystyle \sum_{k=0}^{10^{100}} \left \lfloor \dfrac{X}{10^k} \right \rfloor$ を 正確に 求めよ.

まず, $\displaystyle \left \lfloor \dfrac{X}{10^k} \right \rfloor$ は $X$ の下から $k$ 桁を取り除いた整数である. これらの和を求めたい. そこで, 筆算で求める方法を考えると, 以下のような方法が思い浮かぶ.

$x_1, \dots, x_n$ で $X$ の上から $k$ 桁目の数字が表す整数とし, $y_0=0, y_k=x_1+\dots+x_k$ とする.
$r \gets 0$ (繰り上がりを代入する変数).
の順に以下を行う.
- $z_k \gets (y_k+r) \pmod{10}$
- $\displaystyle r \gets \left \lfloor \dfrac{y_k+r}{10} \right \rfloor$
$z_0 \gets y_0+r$
$z_0 z_1 \dots z_n$ をこのままつなげるとその文字列が表す整数が求めるべき整数になる.