一道ACM题目：求超大数除以1-9的余数
Description:
不可否认，fans 是一名数学天才，大家都这么说。天才 fans 的两大最新发现如下：
（1）正整数 n 除 3 的余数，等价于，正整数 n 的各位数字之和除 3 的余数；
（2）正整数 n 除 9 的余数可以通过这样的方法来计算：
计算 n 的各位数之和，设为 m，如果 m 已经是一位数，那么余数就是 m；否则设 n = m，重新进行计算n的各位数之和 m，
直到 m 是一个一位数。但是，正整数除1，2，4，5，6，7，8，也存在类似的性质吗？这真是一个难题啊！
fans 想睡觉了，不去管了。现在请你计算一下正整数n除一位数 m 的余数。
文件中有一些数对，一为大整数（可能大到100位）n，另一为一位数 m（> 0）。求其 n 除以 m 的余数。
Sample Input:
23 7
123 9
Sample Output:
2
6
[解决办法]
其实个位数乘上2还不如高位数乘上3加上低位数，这样一位位读入数据时就可以处理了
比如
12345345 mod 7
首先
1 mod 7 =1
然后
12 mod 7 = (1*3+2) mod 7=5
然后
123 mod 7 = 5*3+3 mod 7=18 mod 7 = 4
1234 mod 7 = 4*3+4 mod 7 = 16 mod 7 =2
12345 mod 7 = 2*3 +5 mod 7 = 11 mod 7 =4
123453 mod 7 = 4*3 +3 mod 7 = 15 mod 7 =1
1234534 mod 7 = 1*3 +4 mod 7 = 0 mod 7
12345345 mod 7 =0*3 +5 mod 7 =5
而上面的乘数3也可以用10替换，其实所有的数据都可以这样统一处理
[解决办法]
关于对6的算法，我已经说得较明白了，
分别计算该数对2和对3的余数，记为r2、r3，则 r6 = ( 3*r2 + 4*r3 ) % 6
或直接查下表：
r2 \ r3 | 0 1 2
---------+------------------
0 | 0 4 2
1 | 3 1 5
关于对7的算法，我认为还是分段相加再取余的算法效率最高，
因为避免了大数运算，用到除法指令的次数最少（不超过三次），且加减指令的次数也非常少。
（注意：除法指令需要的时钟数是乘法的数十倍，应尽可能避免）
为了减少加法次数，在计算对3或对9的余数时，每次可适当多计算几位。
计算方向可从数字的任意端开始，只是从尾部开始更简单些。
如果该大数非常大（比如有上十亿位），注意在累计和达到一定规模时用一次取余运算以防止溢出。
[解决办法]
不是说按照我说的类似 4)进行分析的吗？
n = a0+10*a1+100*a2+1000*a3+ ...+ 10^(n-1)*a(n-1) , 即a0, a1,a2, a(n-1) 分别表示 n 在十进制下各个位的值。
n%6 = (a0+10*a1+100*a2+1000*a3+ ...+ 10^(n-1)*a(n-1))%6
= ( (a0%6) + (10*a1)%6 + (100*a2)%6 + .... +(10^(n-1)*a(n-1))%6 )%6
= ( a0%6 + (4*a1)%6 +(4*a2)%6 + (4*a3)%6 + ...+ (4*a(n-1))%6 )% 6
= ( a0%6 + (4*(a1+a2+a3+...a(n-1))%6 )%6
即把一个数字的个位数字%6得a, 然后从十位开始，把各个数字相加，然后乘以4，最后取余，得b ,结果等于 (a+b)%6。
举例：
n = 35782; 35782%6 = (2%6 + (4*(8+7+5+3))%6)%6 = (2+(4*23)%6)%6 = (2+92%6)%6 = (2+2)%6 = 4.
======
至于 n % 7 情况
看下面的规律
10 % 7 = 3， 10^2%7 = 2, 10^3%7 = 6, 10^4%7 = 4, 10^5%7 = 5, 10^6%7 = 1 ;
10^7%7 = 3, 10^8%7 = 2,........ 重复出现
计算 n%7 的时候，要看n有多少位，然后根据这个规律计算。
n%6 = (a0+10*a1+100*a2+1000*a3+ ...+ 10^(n-1)*a(n-1))%7
= ( (a0%7) + (10*a1)%7 + (100*a2)%7 + .... +(10^(n-1)*a(n-1))%7 )%7
= ( a0%6 + (3*a1)%7 +(2*a2)%6 + (6*a3)%7 + ... )% 7
通过编程很容易计算，只要依次取每个位的数字，然后按上式计算余数，相加后，在取一次余数（因为这些数的和可能会超过7）。
[解决办法]
对于7而言，每7位可以作为一个循环。因为个位除以7的余数很好算，十位对7的余数等于10对7的余数也就是3，再乘以十位的数。百位数对7的余数为100对7的余数也就是2，再乘以百位数。
以此类推
1对7的余数为1
10对7的余数为3
100对7的余数为2
1000对7的余数为6
10000对7的余数为4
100000对7的余数为5
1000000对7的余数为1
接下来为132645的循环
我的方法是：比如对于23456322这个数字而言
它对7的余数等于((2*1)%7+(2*3)%7+(3*2)%7+(6*6)%7+(5*4)%7+(4*5)%7+（3*1)%7+(2*3)%7)%7=1
结果为1.请大家验证我这个方法。
如果有错的地方请大家指正。
