ABC233 E - Σ
k=0..10^100
floor(X/10^k) (500)
下の位から考える
一番下の位はXの各桁を足した値、二番目に下の位はXの最後の桁を除いたものを足した値になる
なので最下位の位から以下を行う
繰り上がりに今見ている桁までの累積和を足す
10で割ったあまりをその桁として文字列に追加
10で割った商を繰り上がりとして次の桁で使う
最後に繰り上がりがあったらそれを新しい桁として追加
文字列は最下位が最上位に来ている状態なので反転させて出力する
$ X
の桁数分の処理だけなので
$ \mathcal{O}(\log X)
問題:
https://atcoder.jp/contests/abc233/tasks/abc233_e
提出:
https://atcoder.jp/contests/abc233/submissions/28125102
#ABC233
#500pt
#E
#ABC
#AtCoder
#累積和