《孙子算经》中的题目:有物不知其数,三个一数余二,五个一数余三,七个一数又余二,问该物总数几何?
《孙子算经》中的解法:三三数之,取数七十,与余数二相乘;五五数之,取数二十一,与余数三相乘;七七数之,取数十五,与余数二相乘。将诸乘积相加,然后减去一百零五的倍数。
解析:
现在有三个数abc,满足a%3=2,b%5=3,c%7=2。
如果和c都是3的倍数,那么(a+b+c)%3依然对于2。
同理和c都是5的倍数,那么(a+b+c)%5依然等于3。
和b都是7的倍数,那么(a+b+c)%7依然等于2。
假设解为n,n等于abc的和。
那么要满足以上1.2.3.条件。
那么a%3=2,a为5和7的倍数,a最小为35。
同理b最小为63,c最小为30。
n的最小值为(35+63+30)%105=23。
这个105是哪里来的呢?
其实105=357是三者的最小公倍数。
加减整数倍的105,其结果都会满足条件。
《孙子算法》里有三个关键数,这三个关键数分别为70,21,25。
因为如70为5和7的倍数,并且对3取余为1。
(70x+21y+25z)是对3取余为x,对5取余为y,对7取余为z的数,
那么可以反推x等于2,y等于3,z等于2。
在对其对105取余就得到最小的满足条件的值。
所以下次面对类似的题目,可以从关键数出发为突破口。