公考帝

 找回密码
 立即注册
查看: 944|回复: 166

关于中国剩余定理[兼与海盗头子商榷]

  [复制链接]

0

主题

0

帖子

2

积分

办事员

Rank: 1

积分
2
发表于 2007-11-14 13:54:00 | 显示全部楼层 |阅读模式
如果您对于数学比较感兴趣或者曾接触过数奥,请往下看

如果您对于数学十分苦手并且只需要解题方法,请直接前往2楼

首先是对海盗头子所说的中国剩余问题的通用公式进行讨论

原帖地址   https://gongkaodi.com/read-htm-tid-9403341.html


[color=]中国剩余问题定理使用的必要条件是除数必须互质
。否则在运用公式第一步时容易发生得不到解的情况。(海盗在公式中未说明必须互质,而是要扩展为任意数,但是所举的例子中的除数都是互质的)

论证如下:
例如:某数除以3余1,除以6余2,除以9余3
符合这样条件的数是不存在的。因为除以9余3的数仍然是3的整数倍,不会在除以3之后有余数1。
在除以3余1的前提下除以6只能余1或者4,除以9只能余1或者4或者7。

再例:某数除以4余1,除以6余2,除以9余3
仍然没有符合条件的数。原因是除以4余1说明是奇数,除以6余2说明是偶数。又奇又偶的数是啥?

所以改一下:某数除以4余1,除以6余1,除以9余7。基本看不出问题了
套公式…6*9*X除以4余1…又完了

所以我将存在公约数的情况归纳为某数除以X余m,除以aY余n,除以bY余p。因为目的是证明只要除数存在公约数就无法套用公式,所以取有2个数的情况(3个数和2个数的论证没区别,且2个数的情况使用范围更广)
那么在公式1中,要满足X*bY除以aY余1
所以余数肯定是Y的倍数
注意,在这里是讨论余数。不能把分子分母的Y给约了!!6/4的余数是2,但是3/2余数是1
因为是公约数,所以Y不能等于1,否则不成了互质了?
所以在除数间有公约数的情况下,某式子在公式的第一步会得不到余1的解

所以在有公约数的情况下使用您的剩余问题通用公式可能会产生一些问题。
但是,在互质的前提下不会有差错。

从解题的思路来看,海盗所给出的公式是只要符合条件就能套的(论证略),但是因为题干没出好,所以看起来有很多字母。一般人看到公式中的字母数量超过5个就头发昏了,那个公式中涉及了12个
-_-   不要开心,还有9个...

所以我稍微简化了一下,可以帮助记忆。

某数除以A余M,除以B余N,除以C余P,(ABC组为除数,MNP组为余数,XYZ组为凑数所得。接触过奥数的朋友应该感到很亲切吧,余数就喜欢用这个…)则
1.求
B*C的X倍除以A余1    (对应除以A余M)
A*C的Y倍除以C余1    (对应除以B余N)
A*B的Z倍除以B余1    (对应除以C余P)

费时的地方在于XYZ要凑数得到
2.
B*C*X*M+A*C*Y*N+A*B*Z*P=符合条件的数
然后该数减去A、B、C的最小公倍数次直至得到的差小于最小公倍数,那么这个差就是符合条件的最小数

在公式2中注意与1中的对应关系可以使你更容易理解


上一篇:类似这种题怎么选啊
下一篇:求解法
回复

使用道具 举报

0

主题

0

帖子

2

积分

办事员

Rank: 1

积分
2
 楼主| 发表于 2007-11-14 13:55:00 | 显示全部楼层
上面的是需要和海盗头子商榷的问题,
[color=]对于图快而又无法理解的Q友来说,代入法是您最方便、快捷、安全的选择。

下面内容如果你觉得理解有困难…恕某表达不当,请无视。直接看末尾总结即可

根据以往参加奥林匹克数学竞赛的经验,我一直认为,只有在充分理解了公式之后,奇招妙想才会信手拈来。

那么,下面介绍我从该公式中悟到的一个方法,可以有效解决海盗头子所说的

“代入在只要求算出一个数的时候显然是最简单的办法.....不过目前的情况是很多题目是要求一个数值区间内有几个符合条件的数, 这就无法采用代入法了”

的情况。

举例:
例.某数除以3余X,除以4余Y,除以5余Z。求在10000以内符合该条件的数有几个?
为了表现该方法的精髓,所以余数暂时不给出,下一步骤再给。

步骤1,因为3、4、5互质,求3、4、5的最小公倍数。3*4*5=60
步骤2,10000(范围,要绝对范围,如果题干问1000到2000有几个符合条件则用2000-1000来当被除数,但是该情况稍微有点复杂,所以今天不讨论)除以60(最小公倍数)等于166余40

结论1,在该范围中符合条件的数为166或者166+1=167
瞎猜的话该题的正确率可以达到50%。但是这还不能充分满足我们(开玩笑,0.7分可以拉下N个名次的)
所以我们要考虑,在那剩下的40个余数中是不是会有1个数符合题干中的条件,如果没有,则答案为166,有则为167。

这40个数在哪里呢?应该是在166*60与10000之间。为什么?

请翻回公式,看最小的符合条件的数是怎么求得的。是由某符合条件的数减去了最小公倍数的数倍得到的小于最小公倍数的数。所以,该数小于最小公倍数且相邻的两个符合条件之数的差为最小公倍数。

那么,将10000以最小公倍数60为一组开始划分,每组中有且只有1个数是符合条件之数。
但是最后的40个数我们不能确定是不是有符合条件的数在其中。

所以下一步是将剩余数字都写出来看是不是符合条件。
是写9661,9662,9663……吗?
可以,但是太烦。所以我们写1,2,3……39,40就够了

为什么?还是从区间考虑。60个数所构成的区间中必有1个符合条件,所以这种60个数所组成的区间可以任意排布。你可以从1开始到10000来排,或者从10000开始倒着排,其结果是一样的,都是166组。我们现在只要考虑剩下的40个数是不是藏着1个符合条件的数就行。从1到40的取值有利于我们快速解题。

但是40个数仍然嫌多,所以,我们要充分排除一些不可能符合条件的数。
先把XYZ的值取出…取2,2,1好了(我随便取的)

那么题干是某数除以3余2,除以4余2,除以5余1。

请观察,你能想到什么?

在考虑余数问题的时候,要先看除数。这里的除数中,5是一个很好的数字。他说明,在1-40中符合条件的数的个位数肯定是1或者6。
所以你可以在草稿上写上

1,6,11,16,21,26,31,36

好了,8个数。再一看,哎呀~除以4余2这个太好了。被除数肯定是偶数啊

划取所有奇数,剩下

6,16,26,36

恩,再一看,被3除了有余数2,肯定不是3的倍数嘛,6和36去了

剩16和26,请代入解决。

得26是符合条件之解。

好了,所以~某数除以3余2,除以4余2,除以5余1,在10000中符合该条件的数有166+1=167个。


总结,以上的后半部分也可以直接用于求具体的最小数,但是速度根据个人对数字的理解和敏感程度会有很大的差别。所以单独求最小数的时候就代入法好了,选择题的天敌啊…
如果是求某范围中符合条件有几个数,直接拿范围除以最小公约数,然后看人品。当然出题老师傻一点的话可能只有一个选项是符合的,那就是他啦~否则就是二选一~~吼吼


附上一些经验:
一.除以2余1的被除数肯定是奇数(这也是出题者不太可能出的,一眼就把选择范围去掉一半)
   一的进阶:除以2的倍数(如4,6,8……)之后余下的数为奇数的,被除数是奇数;余数是偶数的,被除数是偶数。间接证明了跟2有关的都是好东西。

二.若除以5以后的余数为X,则被除数个位为X或X+5取个位。直接排除了五分之四的选项,比2还好~
   二的进阶:除以10的余数就是被除数的个位数

三.一般老师出题不会很难,大致在10以内出现的比较多,因为足以难倒一般人又不会对有方法的人造成很大困扰,容易看出高下
回复

使用道具 举报

0

主题

47

帖子

125

积分

科长

Rank: 2

积分
125
发表于 2007-11-14 13:57:00 | 显示全部楼层
学习了,剩余定理理解了还是蛮简单的
回复

使用道具 举报

1

主题

17

帖子

69

积分

科长

Rank: 2

积分
69
发表于 2007-11-14 13:59:00 | 显示全部楼层
顶一下,不过我记得海盗在前几行说过,必须互质才行(一会再去看哈)
确实是如果有公约数的话比较麻烦,谢谢互相交流

回复

使用道具 举报

0

主题

0

帖子

2

积分

办事员

Rank: 1

积分
2
 楼主| 发表于 2007-11-14 14:00:00 | 显示全部楼层
欢迎大家提出建议,个人思考所得难免会有所缺漏~
回复

使用道具 举报

1

主题

17

帖子

69

积分

科长

Rank: 2

积分
69
发表于 2007-11-14 14:01:00 | 显示全部楼层
好像确实没说啊,他这个是疏忽了


谢谢LZ分享
回复

使用道具 举报

2

主题

21

帖子

75

积分

科长

Rank: 2

积分
75
发表于 2007-11-14 14:03:00 | 显示全部楼层
我不懂的是关海盗头子什么事
回复

使用道具 举报

0

主题

8

帖子

28

积分

办事员

Rank: 1

积分
28
发表于 2007-11-14 14:06:00 | 显示全部楼层
对楼主表达下崇拜之情

回复

使用道具 举报

0

主题

11

帖子

38

积分

办事员

Rank: 1

积分
38
发表于 2007-11-14 14:06:00 | 显示全部楼层
强啊,跟俺以前的数学老师似的,好方法,多谢

回复

使用道具 举报

1

主题

14

帖子

39

积分

办事员

Rank: 1

积分
39
发表于 2007-11-14 14:09:00 | 显示全部楼层


先占个座...下午比较忙.....有时间再细细斟酌.........

谢谢ycyc的奉献.....
回复

使用道具 举报

1

主题

14

帖子

39

积分

办事员

Rank: 1

积分
39
发表于 2007-11-14 14:32:00 | 显示全部楼层


了解了.....公式我确实没必要用到12个字母, 我自己都看得晕....我就把你的借用啦o^_^

符合条件的数我也是考虑选项有可能出两种的情况, 否则公倍数法当然也是最快的....

总结得很好....我去买花来给你加推荐
回复

使用道具 举报

0

主题

24

帖子

72

积分

科长

Rank: 2

积分
72
发表于 2007-11-14 15:03:00 | 显示全部楼层
如果单单是求数的话,代入法最实惠,准确
如果是求个数的话,就需要有真才实学了
回复

使用道具 举报

0

主题

0

帖子

2

积分

办事员

Rank: 1

积分
2
 楼主| 发表于 2007-11-14 17:04:00 | 显示全部楼层
所以公倍数法的重要瓶颈在怎么样把一堆数快速排除掉

出现5的话就容易了,除非出题老师巨变态,喜欢3,7,11...

反正概率已经增加到50%了,可以随便猜一下拼RP的...
回复

使用道具 举报

0

主题

3

帖子

12

积分

办事员

Rank: 1

积分
12
发表于 2007-11-14 17:05:00 | 显示全部楼层
谢谢楼主~~
回复

使用道具 举报

0

主题

14

帖子

52

积分

科长

Rank: 2

积分
52
发表于 2007-11-14 19:58:00 | 显示全部楼层
谢谢楼主,好方法!
回复

使用道具 举报

0

主题

1

帖子

4

积分

办事员

Rank: 1

积分
4
发表于 2007-11-14 20:49:00 | 显示全部楼层
见识了,,太强了,理论性太强!!
回复

使用道具 举报

0

主题

15

帖子

48

积分

办事员

Rank: 1

积分
48
发表于 2007-11-16 01:45:00 | 显示全部楼层
谢谢楼主,

回复

使用道具 举报

0

主题

16

帖子

56

积分

科长

Rank: 2

积分
56
发表于 2007-11-21 16:03:00 | 显示全部楼层
学习一下 ,LZ

回复

使用道具 举报

0

主题

1

帖子

4

积分

办事员

Rank: 1

积分
4
发表于 2007-11-21 19:34:00 | 显示全部楼层
一个字,晕
好希望有个人当面讲讲啊
回复

使用道具 举报

0

主题

11

帖子

32

积分

办事员

Rank: 1

积分
32
发表于 2007-11-21 19:43:58 | 显示全部楼层
学习了,偶也对楼主表达下崇拜哦

嘎嘎,谢谢楼主了。
回复

使用道具 举报

1

主题

10

帖子

39

积分

办事员

Rank: 1

积分
39
发表于 2007-11-21 20:20:00 | 显示全部楼层
看晕了,楼主这数学也研究得太明白了,佩服
回复

使用道具 举报

0

主题

13

帖子

44

积分

办事员

Rank: 1

积分
44
发表于 2007-11-22 10:14:00 | 显示全部楼层


真是好办法,顶你了楼主,最好有联系巩固一下
回复

使用道具 举报

0

主题

3

帖子

12

积分

办事员

Rank: 1

积分
12
发表于 2007-11-22 13:13:00 | 显示全部楼层


不好意思,我就是急于求成,又无法理解公式的,奥数没接触过


所以直接看了二楼了 o^_^
回复

使用道具 举报

0

主题

6

帖子

22

积分

办事员

Rank: 1

积分
22
发表于 2007-11-23 13:34:00 | 显示全部楼层
非常感谢了,支持支持。。。。。。
回复

使用道具 举报

0

主题

4

帖子

14

积分

办事员

Rank: 1

积分
14
发表于 2007-11-23 13:41:00 | 显示全部楼层
看不懂,实在是迷糊了
回复

使用道具 举报

0

主题

2

帖子

8

积分

办事员

Rank: 1

积分
8
发表于 2007-11-24 16:25:00 | 显示全部楼层
强力支持了,好贴的
回复

使用道具 举报

0

主题

1

帖子

4

积分

办事员

Rank: 1

积分
4
发表于 2007-11-24 17:45:00 | 显示全部楼层
嗯,分析的不错,只是看的时候比较繁琐
回复

使用道具 举报

0

主题

1

帖子

4

积分

办事员

Rank: 1

积分
4
发表于 2007-11-25 22:44:00 | 显示全部楼层


谢谢版主,我终于把这种题目弄明白了
回复

使用道具 举报

0

主题

25

帖子

80

积分

科长

Rank: 2

积分
80
发表于 2007-11-29 02:50:00 | 显示全部楼层
谢谢啦
对您非常崇拜
从小就崇拜数学好的人!
回复

使用道具 举报

0

主题

5

帖子

18

积分

办事员

Rank: 1

积分
18
发表于 2007-11-29 07:48:00 | 显示全部楼层
海盗头子是谁啊
回复

使用道具 举报

0

主题

1

帖子

4

积分

办事员

Rank: 1

积分
4
发表于 2007-11-29 08:22:00 | 显示全部楼层
谢谢重新温习以下了
回复

使用道具 举报

1

主题

33

帖子

97

积分

科长

Rank: 2

积分
97
发表于 2007-11-29 09:05:00 | 显示全部楼层
楼主强的

回复

使用道具 举报

0

主题

1

帖子

4

积分

办事员

Rank: 1

积分
4
发表于 2007-11-29 09:11:00 | 显示全部楼层
顶!!!
楼主牛人,谢谢分享。
回复

使用道具 举报

4

主题

30

帖子

80

积分

科长

Rank: 2

积分
80
发表于 2007-11-29 09:28:00 | 显示全部楼层
看得半懂!呵呵,不过有些东西可借鉴,谢谢了
回复

使用道具 举报

0

主题

1

帖子

4

积分

办事员

Rank: 1

积分
4
发表于 2007-11-29 10:01:00 | 显示全部楼层
很好的東西,收下了。
回复

使用道具 举报

0

主题

11

帖子

28

积分

办事员

Rank: 1

积分
28
发表于 2007-11-29 16:08:00 | 显示全部楼层
出现除数不互质的情况怎么办.
例如:一个数除10余9,除9余8,除8余7,求这个数.
回复

使用道具 举报

0

主题

1

帖子

4

积分

办事员

Rank: 1

积分
4
发表于 2007-11-29 19:14:00 | 显示全部楼层
学习了
回复

使用道具 举报

0

主题

15

帖子

42

积分

办事员

Rank: 1

积分
42
发表于 2007-11-29 21:37:00 | 显示全部楼层
支持一下!


回复

使用道具 举报

0

主题

3

帖子

10

积分

办事员

Rank: 1

积分
10
发表于 2007-11-29 22:53:15 | 显示全部楼层
比较费时的,留日后在看!受教了,谢谢楼主

回复

使用道具 举报

0

主题

24

帖子

70

积分

科长

Rank: 2

积分
70
发表于 2007-12-1 00:05:00 | 显示全部楼层
领受了~~~!~~
一定要记牢了才对得起2位的奉献精神~~
回复

使用道具 举报

0

主题

2

帖子

8

积分

办事员

Rank: 1

积分
8
发表于 2007-12-1 01:11:00 | 显示全部楼层


占个座,先睡个觉明天再来
回复

使用道具 举报

0

主题

2

帖子

6

积分

办事员

Rank: 1

积分
6
发表于 2007-12-3 14:31:00 | 显示全部楼层
占位学习........................
回复

使用道具 举报

0

主题

2

帖子

6

积分

办事员

Rank: 1

积分
6
发表于 2007-12-3 14:41:00 | 显示全部楼层
还是不懂

回复

使用道具 举报

0

主题

2

帖子

6

积分

办事员

Rank: 1

积分
6
发表于 2007-12-4 16:17:00 | 显示全部楼层
呵呵 好好学习下
回复

使用道具 举报

0

主题

1

帖子

4

积分

办事员

Rank: 1

积分
4
发表于 2007-12-4 16:27:00 | 显示全部楼层
第一楼的东西好难懂~
回复

使用道具 举报

0

主题

1

帖子

4

积分

办事员

Rank: 1

积分
4
发表于 2007-12-4 16:34:00 | 显示全部楼层
你给这个数+1 它不就能整除 10  9  8  了吗
就是360-1=359
回复

使用道具 举报

0

主题

1

帖子

4

积分

办事员

Rank: 1

积分
4
发表于 2007-12-13 18:30:00 | 显示全部楼层
崇拜
回复

使用道具 举报

0

主题

1

帖子

4

积分

办事员

Rank: 1

积分
4
发表于 2007-12-13 20:26:00 | 显示全部楼层
真是好贴啊。对我受益匪浅啊。

回复

使用道具 举报

0

主题

1

帖子

4

积分

办事员

Rank: 1

积分
4
发表于 2007-12-14 09:12:00 | 显示全部楼层
几乎晕。。

回复

使用道具 举报

0

主题

3

帖子

12

积分

办事员

Rank: 1

积分
12
发表于 2007-12-14 09:58:00 | 显示全部楼层
掌握这个对考公务员真的有帮助 ???
回复

使用道具 举报

您需要登录后才可以回帖 登录 | 立即注册

本版积分规则

Archiver|手机版|小黑屋|公考帝 |网站地图

GMT+8, 2021-9-26 14:41 , Processed in 0.843201 second(s), 42 queries .

Powered by Discuz! X3.4

© 2001-2017 Comsenz Inc. Template By 【未来科技】【 www.wekei.cn 】

快速回复 返回顶部 返回列表