华电北风吹
天津大学认知计算与应用重点实验室
日期：2015/8/24

先说一下结论

有k<script type="math/tex" id="MathJax-Element-1">k</script>进制数abcd<script type="math/tex" id="MathJax-Element-2">abcd</script>，有abcd%(k?1)=(a+b+c+d)%(k?1)<script type="math/tex" id="MathJax-Element-3">abcd\%(k-1)=(a+b+c+d)\%(k-1)</script>
这是由于kn=((k?1)+1)n=∑ni=0Cin(k?1)i<script type="math/tex" id="MathJax-Element-4">k^n=((k-1)+1)^n=\sum_{i=0}^n{C^i_n}(k-1)^i</script> 因此kn<script type="math/tex" id="MathJax-Element-5">k^n</script> 对(k-1)取余的话为1

比如10进制1425%9=3，(1+4+2+5)=12%9=3.

这个性质眼下我在两个地方见到了
（一）算法导论第11章讲散列表的时候，除法散列的时候
h(k)=k<script type="math/tex" id="MathJax-Element-6">h(k)=k</script>mod m<script type="math/tex" id="MathJax-Element-7">m</script>
对于m的选取，若m取2p<script type="math/tex" id="MathJax-Element-8">2^p</script>或者2p?1<script type="math/tex" id="MathJax-Element-9">2^p-1</script> 均是不合适的选择，前者是由于有低p位决定散列函数值。后者是由于仅仅于大于p位出现的数字有关，而于顺序无关。
（二）Leetcode刷题
Leetcode258题
Given a non-negative integer num, repeatedly add all its digits until the result has only one digit.
For example:
Given num = 38, the process is like: 3 + 8 = 11, 1 + 1 = 2. Since 2 has only one digit, return it.
这个的思路是循环利用前面说过的结论
所以对于给的非负整数，仅仅须要对9取余就可以，须要考虑整除的时候返回9，而仅仅当输入是0的时候返回0

https://en.wikipedia.org/wiki/Digital_root
https://leetcode.com/problems/add-digits/