《任何一个整数模9同余于它的各数位上数字之和》

2019-04-13 12:13发布

站内文章 / 模拟电子
12468 0 1060
在做https://leetcode.com/problems/add-digits/这道题时，发现了这个问题。即
任何一个整数模9同余与它的各数位上的数字之和。 具体证明过程如下： 　　设自然数N=a[n]a[n-1]…a[0]，其中a[0]，a[1]、…、a[n]分别是个位、十位、…上的数字 　　再设M=a[0]+a[1]+…+a[n] 　　求证：N≡M(mod 9). 　证明： 　　 ∵ N=a[n]a[n-1]…a[0]=a[n]*10^n+a[n-1]*10^(n-1)+…+a[1]*10+a[0]. 　　 又∵ 1≡1(mod 9), 　　 10≡1(mod 9), 　　 10^2≡1(mod 9), 　　 … 　　 10^n≡1(mod 9). 　　 上面这些同余式两边分别同乘以a[0]、a[1]、a[2]、…、a[n]，再相加得： 　　　　 a[0]+a[1]*10+…+a[n]*10^n≡(a[0]+a[1]+…+a[n])(mod 9)， 　　　　　　　　　　　　　　　　 即 N≡M(mod 9)，得证。 　　有了这个性质就容易解决本题了 　　在计算过程中，可以不断mod 9，因为我们知道有这样两个性质： 　　　　(A+B)mod C = （(A mod C) + (B mod C)）mod C 　　　　(AB)mod C = ((A mod C)×(B mod C)) mod C 　还要注意，如果余数为0，则输出9 参考地址：http://www.cnblogs.com/Rinyo/archive/2012/12/20/2826755.html

热门文章