把韩信点兵问题再换个更简单的说法,就是说,有个数除3余2,除5余3,除7余2,问你这个数字最小是几?也可以给定一个范围,问你是几。 这类问题,纠结应该怎么下手解决呢?对于这样的问题,要先观察,是否存在规律,如果符合一定的规律,则可以通过简单口诀来实现;如果没有规律,那么就要通过一些特殊方法处理。 一、有规律问题的解法 重要口诀:和同加和,差同减差,余同取余,最小公倍加 先来说说最后一句,最小公倍加,意思是,不管什么情况,先把最小公倍数求出来,这个是作为基础。然后根据不同情况进行辨别,如何继续处理。 (一)和同加和 意思是,如果不同被除数和余数的和相同,那么就把这个和,加到最小公倍数上。 例:一个数除5余3,除6余2,除7余1 解题思路:5、6、7的最小公倍数是210,因为5+3=6+2=7+1=8,所以这个数最小就是8,其余满足条件的数字是210的倍数+8,比如218、428…… (二)差同减差 意思是,如果不同被除数和余数的差相同,那么就把这个差,用最小公倍数减掉。 例:一个数除5余3,除6余4,除7余5 解题思路:5、6、7的最小公倍数是210,因为5-3=6-4=7-5=2,所以这个数最小就是:210-2=208,其余满足条件的数字是210的倍数+208,比如418、628…… (三)余同取余 这个是最简单的了,意思是,如果余数都相同,直接把余数加到最小公倍数上。 例:一个数除5余3,除6余3,除7余3 解题思路:5、6、7的最小公倍数是210,所以这个数最小就是3,其余满足条件的数字是210的倍数+3,比如213、423…… 二、无规律问题的解法 一筐苹果,如果按5个一堆放,最后多出2个;如果按6个一堆放,最后多3个;如果按7个一堆放,还多出1个。这筐苹果至少有几个? (一)逐步约束法 5余2的最小数字是7,看看7除以6是余1不是3,所以要看看7上面加多少个5才能除以6余3。 通常的做法是,7+5=12,余0,不对;12+5=17,余5,不对;17+5=22,余4,不对;22+5=27,余3,对了!所以是27。 实际上,也可以用这样的做法,就是:把除以6余3看成是-3(3-6=-3),5除以6余-1。问题就简化为:要把7除以6的余数1变成余-3,需要多少个5除以6的-1?很明显,答案是:(-3-1)÷(-1)=4,也就是说,要在7上面加4个5,也就是加上20,则结果为27 27这个数字出来了,还没结束,下面考虑27除以7余6,不是余1。要在27上面加多少个30(5和6的最小公倍数)才能余1? 同样的思路,要余1,相当于余8(1+7=8),由于30除以7余2,问题就转换为,要从余6变成余8,需要多少个2,答案是1个,也就是27上面加1个30即可,最终数字是57。 (二)中国剩余定律 先找出6和7的公倍数,从中选取一个最小的、能够除以5余1的数字,为42×3=126,用这个数乘以5的余数。题目中除以5余2,所以126×3=252; 再找出5和7的公倍数,从中选取一个最小的、能够除以6余1的数字,为35×5=175,用这个数乘以6的余数。题目中除以6余3,所以175×3=525; 再找出5和6的公倍数,从中选取一个最小的、能够除以7余1的数字,为30×4=120,用这个数乘以7的余数。题目中除以7余1,所以120×1=120; 上述3个数字相加:252+525+120=897 897除以5、6、7三个数的最小公倍数210的余数,即为最终答案:897-210×4=57 三、韩信点兵 回到文章开头韩信点兵的故事,已知军队人数大概在1000-1100左右,如果1-3报数余2人,1-5报数余3人,1-7报数余2人 这个题目我们采用混合做法,既然除以3余2,除以7余2,那么利用同余取余,秒算出来21+2=23 然后,看23除以5余3,正好,不用再加21了,答案就是23,多么简单。 考虑到人数在1000-1100之间,23的基础上加上10个3、5、7的公倍数105,也就是23+10×105=1073 |
|