作业帮韩信点兵,被3除余2,被8除余7,被11除余10的最小自然数
来源：学生作业帮助网 编辑：作业帮 时间：2024/05/06 03:49:01
韩信点兵,被3除余2,被8除余7,被11除余10的最小自然数
韩信点兵,被3除余2,被8除余7,被11除余10的最小自然数
韩信点兵,被3除余2,被8除余7,被11除余10的最小自然数
263
依题这个数比3、8、11的最小公倍数少1
3*8*11-1=263
如果满意望采纳！
"某自然数被3除余2，被8除余7，被11除10"
通过这个条件可以发现这个自然数加1就可以整除3、8、11
而3、8、11的最小公约数是3*8*11=264
所以所求的自然数是264-1=263
设其为t=a*3*8+b*3*11+c*8*11 (a,b,c为正整数)
t mod(3)=c*8*11 mod(3)=c mod(3)=2
所以c=2
t mod(8)=b*3*11 mod(8)=b mod(8)=7
所以b=7
t mod(11)=a*3*8 mod(11)=2a mod(11)=10
所以a=5
可知t0=5*3*8+...
全部展开
设其为t=a*3*8+b*3*11+c*8*11 (a,b,c为正整数)
t mod(3)=c*8*11 mod(3)=c mod(3)=2
所以c=2
t mod(8)=b*3*11 mod(8)=b mod(8)=7
所以b=7
t mod(11)=a*3*8 mod(11)=2a mod(11)=10
所以a=5
可知t0=5*3*8+7*3*11+2*8*11=527
又因为3*8*11=264
所以，t的最小值为527 mod(264)=263
韩信点兵并不是拿另两个除数除乘以这个数的余数就行了。
其实，它的标准形式是 k*r*y*z mod(x)=r 也就是k*y*z mod(x)=1
x,y,z为三个除数，r为除x的余数，k是系数。
如果这一题用这种来做，可得k[x]=k[y]=1;k[z]=6
在标准的韩信点兵里，也不是k[x]=k[y]=k[z]=1，只有这时才能均用另两个除数除乘以这个数的余数就行了。而是k[x]=2;k[y]=k[z]=1。所以口诀中是“三人同行七十稀”，而不是三十五稀。
所以这个可以给她编一个
三人同行八十八， （1*11*8）
八树梅花三十三， （1*3*11）
十一对着一四四， （6*3*8）
除二六四便得之。
这种题的通用解法为，先找两个除数的乘积，看它的几倍除以第三个除数的余数为1。
比如韩信点兵中，5*7=35除3余2，（5*7 mod(3)=2）不符合要求，但35的2倍70除3余1，所以用70。
然后3*7 mod(5)=1符合要求，3*5 mod(7)=1符合要求，所以用70，21，15。
韩信点兵的口诀就是这样造的，其实，韩信点兵是今天基本算法中的例子，用前面那个更简便些。
收起