腾讯teg云架构凉经

首先说一个概念，任意自然数N，其各位数字相加之和为M，那么N与M对模3同余。根据同余定理，可以先对N的每一位数字除以3取余，再相加后除以3取余，结果依然和N直接除以3取余相同。举个例子1234567除以3余1，1+2+3+4+5+6+7 = 28除以3余1。分别对计算1-7除以3的余数再相加，得到1+2+0+1+2+0+1 = 7除以3余1。这里的数学原理其实很简单，我们令个位数字是第0位，十位数字是第1位，百位数字是第2位，以此类推。假设自然数N的第i位数字是n，那么这位数字n实际代表的数是n乘以10的i次方。注意到10的i次方减去1得到999...99（i个9）必然被3整除，因此10^i ...