韩信点兵&取余运算&剩余定理

韩信带兵1500人去打仗，战死四五百人。战后清点人数时，韩信命令士兵每3人站一排，多出2人；每5人站一排，多出3人；每7人站一排，多出2人。请问这支部队在战后还有多少人？

这道题我们用数学语言表述（从现实问题抽象成纯数学问题），即为：有一个数字，除以3余2，除以5余3，除以7余2，那么这个数字是多少？

求解这道题最基本的方法便是穷举法，把满足每个条件的数字写出来，然后找到相同的数字即可。

1、除以3余2的数字有：2、5、8、11、14、17、20、23、26…

我们发现，满足上述三个条件的第一个数字是23，所以23是这道题的第一个解。但，很显然，23并不是唯一解。条件中的三个除数3、5、7刚好彼此互质，它们的最小公倍数便是3*5*7=105。

也可以说，105除以3、5或者7都没有余数。因此，符合题目条件的数即为23+105n，其中，n=1，2，3…。

再根据题目条件韩信带兵1500人，战死四五百，那么战后人数在1000~1100之间，最终可得出n=10，这支部队在战后还有23+105*10=1073人。

那如果没摸索出规律，得不到通解怎么办呢？如果用笨方法，从1000开始一个个判断是否满足条件，工程量浩大，也容易出错。这时候我们就可以通过Scratch编程，利用计算机的高效计算帮助我们求解。

解决了“韩信点兵”，再来一道来自明代数学家程大位《算法统宗》中的题考考你：正月十五元宵节，街上赏灯的人来来往往。有一座花灯，若是从顶端往下数，3盏3盏地数正好数尽，5盏5盏地数还剩4盏，7盏7盏地数还剩6盏。请问这座花灯从头到底一共有几盏灯笼？

这个题以前让大家做过，同样需要使用穷举法，相信你一定可以解答出来。

在西方德国数学家高斯于公元1801年出版的《算术探究》中明确地写出了上述定理。公元1852年，英国基督教士伟烈亚士将《孙子算经》“物不知数”问题的解法传到欧洲，公元1874年马蒂生指出孙子的解法符合高斯的定理，从而在西方的数学史里将这一个定理称为“中国的剩余定理”。

余数在不少方面也有很重要的应用，比如在计算机、网络上传输数据，为了保证数据的准确性，就有用余数原理作为检验的方法。

再比如我国18位的二代身份证号码，也采用了余数检查的方法

二代身份证中的校验码是身份证号码的最后一位，是根据国家统一的标准按照一套规则算出来的。具体的计算方法是

1、将身份证号码前17位数按下表每位数分别乘以对应的乘数；

2、将这17个乘积的结果相加；

3、用加出来和除以11，看余数是多少；

4、余数只可能有0~10这11个数，按下表找出对应的最后一位身份证的号码，其中的X是罗马数字10。

假设有一个在2008年北京奥运会开幕当天出生的北京市的男同学身份证号前17位是11010820080808287，那么计算校验码的过程是：

7*1+9*1+10*0+5*1+8*0+4*8+2*2+1*0+6*0+3*8+7*0+9*8+10*0+5*8+8*2+4*8+2*7=255
255÷11=23……2

查表，余数2对应的校验码就是X，所以完整的身份证号码应该是11010820080808287X

虽然这样计算看起来有些麻烦，但是可以非常有效地把两种最常见的身份证错号的现象判断出来：

一是某位的数字错了，二是两位相邻的数字写反了。

甚至如果知道哪位数字错误，还可以利用校验方法反推出来呢！

那么为什么要采用11这个数字作为除数呢？11是大于10的数字中最小的质数，这是一个非常重要的原因，而深入的道理等同学们的知识积累到更多的时候就可以理解了。

17位数据在编程猫里会出现数据溢出，选择了makeblock

C++程序：

#include<bits/stdc++.h>
using namespace std;
int main(){
long long n;
int a[20]={1,2,4,8,5,10,9,7,3,6,1,2,4,8,5,10,9,7};
int b[13]={1,0,10,9,8,7,6,5,4,3,2},ans,m=-1;
cin>>n;
for(int i=1;i<=17;i++){
ans+=n%10*a[i];
n/=10;
}
m=b[ans%11];
cout<<m;
return 0;
}