中国剩余定理？？？

kee020041

相当出名的一道题目：

有一堆糖果，
　　如果平分给＿＿＿个小孩，还剩下(余)＿＿粒
                ７                    ２
                ５                    ３
                ３                    ２


请问共有多少粒糖果（必需少过７*５*３＝１０５粒）

[ Last edited by kee020041 on 25-4-2005 at 05:55 PM ]

neow_wy

23粒

7个人 X 3粒 + 2粒 = 23粒
5个人 X 4粒 + 3粒 = 23粒
3个人 X 7粒 + 2粒 = 23粒

柏杨

答案是23吧

我的解法是中国剩余定理的,

有哪位高手可以解释别的方法吗?

fritlizt

柏杨 于 25-4-2005 07:32 PM  说 :
答案是23吧

我的解法是中国剩余定理的,

有哪位高手可以解释别的方法吗?

这个我也是用剩余定理来解的。。。。。

neow_wy

中国剩余定理是什么来的？？可以解释一下吗？？

DeadCow

三人同行七十稀
五树梅花廿一枝
7 子团圆正半月
除百零五便得知


应该是用这口诀吧？

希望你们明白怎样用，迟点我再来解释

fritlizt

neow_wy 于 26-4-2005 12:10 AM  说 :
中国剩余定理是什么来的？？可以解释一下吗？？

如果平分给＿＿＿个小孩，还剩下(余)＿＿粒
                ７                    ２
                ５                    ３
                ３                    ２

那五和三的倍数，和能被七除再余二的。 30
那七和三的倍数，和能被五除再余三的。 63
那五和七的倍数，和能被三除再余二的。 35

答案= 30+63+35 = 128
128减掉七，三，和五的公倍数 = 128-105 = 23

kee020041

DeadCow 于 26-4-2005 01:15 AM  说 :
三人同行七十稀
五树梅花廿一枝
7 子团圆正半月
除百零五便得知


应该是用这口诀吧？

希望你们明白怎样用，迟点我再来解释

答案 = 3的余数 X 70 + 5的余数 X 21 + 7的余数 X 15 - 105K              
                           
                   ；K必需 是正整数， 且要使答案小过105
       = 2 X 70 + 3 X 21 + 2 X 15 -105K               
      =233 - 105K            ； K=2
     =233 - 210
    = 23

kee020041

但是；大家又知不知
７０，２１，１５ 是如何算出来的呢？

fritlizt

kee020041 于 26-4-2005 10:10 AM  说 :
但是；大家又知不知
７０，２１，１５ 是如何算出来的呢？

70/3 余 1
21/5 余 1
15/7 余 1

kee020041

General解法：

i = 3的余数
j = 5的余数
h= 7的余数
a,b,c = 正整数
X ＝ 答案


X = 3a + i            ------------------(1)
X = 5b + j            ------------------(2)
X = 7C + K            ------------------(3)


(1)*70   :   70X = 105(2a) + 70i         ----------(4)
(2)*21   :   21X = 105(b)  + 21j         ----------(5)
(3)*15   :   15X = 105(c)  + 15h         ----------(6)


(4)+(5)+(6):

            106X = 105(2a + b + c) + 70i + 21j + 15h

又是；   X +105X = 105(2a + b + c) + 70i + 21j + 15h


所以；


X ＝ 3的余数X70 + 5的余数X21 + 7的余数X15 - 105(X-(2a+b+c))

X ＝ 3的余数X70 + 5的余数X21 + 7的余数X15 - 105K  ；K＝X(2a+b+c)

kee020041

kee020041 于 25-4-2005 05:32 PM  说 :
有一堆糖果，
　　如果平分给＿＿＿个小孩，还剩下(余)＿＿粒
                ７                    ２
                ５                    ３
                ３                    ２

...

用同样方法；如果把题目改成


有一堆糖果，
　　如果平分给＿＿＿个小孩，还剩下(余)＿＿粒
                ５                    ２
                ４                    ３
                ３                    ２


大家又能不能找到：
（１）  答案？
（２）  ３，４，５各自的乘数?（ps:3,5,7各自的乘数是70,21,15)

fritlizt

kee020041 于 26-4-2005 07:06 PM  说 :



用同样方法；如果把题目改成


有一堆糖果，
　　如果平分给＿＿＿个小孩，还剩下(余)＿＿粒
                ５                    ２
                ４                    ３
                ...

那五和三的倍数，和能被四除再余三的。 15
那四和三的倍数，和能被五除再余二的。 12
那五和四的倍数，和能被三除再余二的。 20

答案= 15+12+20 = 47

kee020041

fritlizt 于 26-4-2005 07:13 PM  说 :



那五和三的倍数，和能被四除再余三的。 15
那四和三的倍数，和能被五除再余二的。 12
那五和四的倍数，和能被三除再余二的。 20

答案= 15+12+20 = 47

佩服！佩服！但３，４，５的乘数呢？

fritlizt

kee020041 于 26-4-2005 07:20 PM  说 :



佩服！佩服！但３，４，５的乘数呢？

我减缩了那个方法。不需用乘数来找。
所以我的方法里没有乘数。

kee020041

fritlizt 于 26-4-2005 07:25 PM  说 :


我减缩了那个方法。不需用乘数来找。
所以我的方法里没有乘数。

能解释你的方法吗？懒惰去想！

fritlizt

拿这题来做。
如果平分给＿＿＿个小孩，还剩下(余)＿＿粒
                ７                    ２
                ５                    ３
                ３                    ２


答案 = 3的余数 X 70 + 5的余数 X 21 + 7的余数 X 15

70 就是 7和5的倍数，又是除三余一。
如果拿三的余数来乘的话， 这个数就一定是除三就会余二。

如果我不找乘数， 我可以直接找5和7的倍数， 又能除三余二的。
最小就是35 了。。。。

如此类推，
七和三的倍数，和能被五除再余三的。= 63
五和三的倍数，和能被七除再余二的。= 30

答案就等于 63+35+30 = 128
在减那三个数的最小公倍数 = 105
128-105 = 23 了。
如果得到的答案已小过最小公倍数，那就是答案了。