E - Σ[k=0..10^100]floor(X/10^k) 解説 by Kiri8128


We will explain an easy (and short) implementation with arbitrary-precision integer calculation (like in Python).

Let \(X_i\) be the \(i\) th smallest digit of \(X\). Let \(\displaystyle s = \sum_{i}{X_i}\) be the sum of all \(X_i\) ’s. Now what we need is

\(\displaystyle \sum_{k=0}^{\infty} \left \lfloor \frac{X}{10^k} \right \rfloor\)

\(=\displaystyle \sum_{k=0}^{\infty} \frac{X}{10^k} - \sum_{k=0}^{\infty} \frac{X\bmod 10^k}{10^k}\)

\(=\displaystyle \sum_{k=0}^{\infty} \frac{X}{10^k} - \sum_{i}\sum_{k=1}^{\infty} \frac{X_i}{10^k}\)

\(=\displaystyle \frac{10X}{9} - \sum_{i}\frac{X_i}{9}\)

\(=\displaystyle \frac{10X-s}{9}\)

AC code(PyPy3)

投稿日時:
最終更新: