PKU1519-Digital Roots

題目：http://poj.org/problem?id=1519
將一個數字各個位數加總
如果總和不是一位數(大於9)，那麼再作一次各數字加總…
直到一位數，是為Digital Root
對給出的n問它的Digital Root是多少


程式碼：http://codepad.org/ZVfZ8MHA

輸入沒給範圍，似乎有大數…？
但無論如何我們很容易想到一個偏門的方法：
「把所有位數加起來，並且取mod 9」

於是成了簡單模運算的問題

請看一下這個算式：
a*1000 + b*100 + c*10 + d
也就是四位數abcd的表示
很容易得到
a*1000 + b*100 + c*10 + d ≡ a+b+c+d (mod 9)
顯然這對五位數、六位數、所有十進位數都是成立的

這告訴我們什麼呢？就是一個數字它的DR和mod 9以後的DR是一樣的

最後注意到mod完變成0的意思，在本題就是指答案是9