概要

TGC003，いかがでしたでしょうか．

今回は，実装は軽く心地よく！をモットーに問題セットを構成しました．

問題によっては「実装つらいよ～～」となった方もいらっしゃったかもしれません．
「ひょっとしたらもっと実装が簡単な方針があったのではないか」と考えてみるといいかも？

問題原案：uni_kakurenbo

解説

任意の非負整数 $x$ について，「$x$ の各桁の和を $9$ で割ったあまり」は「$x$ そのものを $9$ で割ったあまり」に一致することが知られています．

したがって，答えは $X \bmod 9$ に等しいです．

---

このことを証明しましょう．

非負整数 $x$ の $10^d \scriptsize \; (0 \leq d)$ の位を $D_d$ と書くことにします．$\scriptsize (0 \leq D_d < 10)$
このとき

• $\displaystyle x = \sum_{0 \leq d} D_d \times 10^d$

です．

任意の $3$ 非負整数 $a, b, k$ について $a \equiv b \Leftrightarrow a^k \equiv b^k$ であることを用いると，

• $\displaystyle x \equiv \sum_{0 \leq d} D_d \times 10^d \equiv \sum_{0 \leq d} D_d \times 1^d \equiv \sum_{0 \leq d} D_d \pmod 9$

が得られます．

解説：uni_kakurenbo

実装例