给定一个非负的整数，求他的各个位的和，然后对这个新数字再求和，直到最后只剩下一位数为止
比如给定12345,各位之和是1+2+3+4+5=15,再算1+5=6,所以12345对应的就是6
能不能把时间复杂度优化到o(1)呢？
很明显最简单的方法就是，用循环来执行求和，时间复杂度是o(logn)
那怎么把时间复杂度优化到o(1)呢？
只有一位数的情况
首先考虑最简单情况，就是只有一个数字，那就不用求了，直接返回这个数字就行了，取值范围是0-9
如果是两位数呢
然后是两位数字的情况,两位的数字是从10-99,那这个数和最大也还是9,因为考虑最大99:9+9=18,1+8=9,那还是9,但是最小的就不是0了，而是1因为可以出现10或者20这种情况，但是不能出现01,02这样的情况
如果是更多位的数呢？
不难想到，那怕是10000位数相加，那加到最后一位也应该是1-9这个范围之内，因为在十进制下只有0-9这10个数字能用，你不可能出现一百二十十这种情况
好像有点规律了
这时可能就有点规律了，这个各位数和在数字大于0的时候就只能是1-9这个范围啊，因为比一位数以上的数字都不可以出现001,002这种情况，不然就不是大于1位的数字了，而且既然这么多的数字，从10-99也有90个数呢，居然只对应9个数，那就很难不让人想到，他们是不是满足一对应关系，就比如做为各位数和的1-9每个对应10个数
因此，我们可以来找一下规律
刚才发现，99的各位数和加起来是9,那么还有没有其它同样是9的数字呢？我们可以列出来是:
18,27,36,45,54,63,72,81,99
为了发现规律，我们可以10-99其它数学和的数字都列出来
| 各位数和 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |
| 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | |
| 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 | 27 | |
| 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 | 36 | |
| 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 | 45 | |
| 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 | 54 | |
| 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 | 63 | |
| 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 | 72 | |
| 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 | 81 | |
| 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 | 90 | |
| 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 | 99 |
将这些数字按照相同各位数和排列在一起，我们好像可以发现规律了：
各位数和为9的列，他的所有数字都是9的倍数，同行的数字都是在这个9的倍数基础上做减法，同列相邻的两个数字之间都相差9，为了搞定他们的规律，我们可以用9列做为基准列，然后将其它列按照数字大小的顺序排列好，我们就会得到
| 各位数和 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 |
| 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 |
| 18 | 19 | 20 | 21 | 22 | 23 | 24 | 25 | 26 |
| 27 | 28 | 29 | 30 | 31 | 32 | 33 | 34 | 35 |
| 36 | 37 | 38 | 39 | 40 | 41 | 42 | 43 | 44 |
| 45 | 46 | 47 | 48 | 49 | 50 | 51 | 52 | 53 |
| 54 | 55 | 56 | 57 | 58 | 59 | 60 | 61 | 62 |
| 63 | 64 | 65 | 66 | 67 | 68 | 69 | 70 | 71 |
| 72 | 73 | 74 | 75 | 76 | 77 | 78 | 79 | 80 |
| 81 | 82 | 83 | 84 | 85 | 86 | 87 | 88 | 89 |
| 90 | 91 | 92 | 93 | 94 | 95 | 96 | 97 | 98 |
| 99 |
我们可以看到 ，在同行内，和9倍数的差值决定了这个数各位数和的多少，比如“3”列，无论是12,21,30,他和同行的9,18,30都只相差3也就是说，和同行的9的倍数相差几，也就是，我们只需要把这个数字除以9,然后看余数是多少，这就是我们要求的各位数和，而在C语言里面，正好有一个运算符【%】可以直接求余数
那么解题思路就很明显了，对于不为0的所有数字，我们只需要求他和9的余数，这样我们就把一个需要循环的o(logn)问题转化成了o(1)问题,但是这里有一个问题就是，如果这个数本身就是9的倍数怎么办，总不能返回0吧
用18来说明，直接对9取余就会输出0,但是他旁边的17对9取余后是8啊，我们可以先给18减去1，对9取余后再加回来，这样我们就能达到曲线救国的效果了
我们可以用代码实现这个过程
int addsums(int num) {
return (num - 1) % 9 + 1;
}
ok，至此我们这已经解决了这个问题，说实话我很喜欢做这种问题，因为在解决问题的过程中可以连带着学到很多新的知识，像是本题就用到了【同余】这个概念，这个可以详细说一下
上面提到过，所谓【同余】看字面意思就是【相同余数】，如果用专业一点的数学知识来讲的话就是，如果有整数a、b、m，存在一个整数k，满足a-b=km，那我们就可以说，a和b对m同余，记为
在这里写上一些同余的性质还有应用的链接，毕竟首先确保会用就行，原理之类的可以作为兴趣再研究
吉公网安备22032302000080号