- 1、本文档共27页,可阅读全部内容。
- 2、有哪些信誉好的足球投注网站(book118)网站文档一经付费(服务费),不意味着购买了该文档的版权,仅供个人/单位学习、研究之用,不得用于商业用途,未经授权,严禁复制、发行、汇编、翻译或者网络传播等,侵权必究。
- 3、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。如您付费,意味着您自己接受本站规则且自行承担风险,本站不退款、不进行额外附加服务;查看《如何避免下载的几个坑》。如果您已付费下载过本站文档,您可以点击 这里二次下载。
- 4、如文档侵犯商业秘密、侵犯著作权、侵犯人身权等,请点击“版权申诉”(推荐),也可以打举报电话:400-050-0827(电话支持时间:9:00-18:30)。
查看更多
中国剩余定理 扩展欧几里德定理 看过《射雕英雄传》的同学应该记得,当年黄蓉身中奇毒,郭靖将她送到瑛姑那里救治,进入瑛姑茅舍,瑛姑就给他们出了一题: “今有物不知其数,三三数之剩二;五五数之剩三:七七数之剩二。问物几何?” 黄蓉天资聪慧,哪里难得住她,她略微思考,答:23。 大家是不是很好奇,黄蓉是怎么解出这道题的呢? 其实,这就是享誉中外的《中国剩余定理》。 一、剩余问题 在整数除法里,一个数同时除以几个数,整数商后,均有剩余;已知各除数及其对应的余数,从而要求出适合条件的这个被除数的问题,叫做剩余问题。 古代人的解法: 凡三三数之剩一,则置七十;五五数之剩一,则置二十一;七七数之剩一则置十五;一百六以上,以一百零五减之即得。 依定理译成算式解为: 70×2+21×3+15×2=233 233-105×2=23 一些关于中国剩余定理的定理: 定理1:几个数相加,如果只有一个加数,不能被数a整除,而其他加数均能被数a整除,那么它们的和,就不能被数a整除。 如:10能被5整除,15能被5整除,但7不能被5整除,所以(10+15+7)不能被5整除。 一些关于中国剩余定理的定理: 定理2:二数不能整除,若被除数扩大(或缩小)了几倍,而除数不变,则其余数也同时扩大(或缩小)相同的倍数(余数必小于除数)。 如:22÷7=3……1 (22×4)÷7=12……1×4(=4) (要余2即 22×2÷7=6……2) (22×9)÷7=28……1×9-7(=2) (想余5则22×5÷7=15……5) 现在人的解法: 用各除数的“基础数”法解。 基础数的条件: (1)此数必须符合除数自身的余数条件; (2)此数必须是其他所有各除数的公倍数。 第一步: 求各除数的最小公倍数 [3,5,7]=105 第二步: 求各除数的基础数 (1)[3] 105÷3=35 [35]÷3=11……2 (2)[5] 105 ÷ 5=21 21÷5=4……1(当于3) ∵1×3=3 21×3=[63] (3)[7] 105 ÷ 7=15 15 ÷ 7=2……1(当于2) ∵1×2=2 ∴15×2=[30] 第三步: 求各基础数的和 35+63+30=128 第四步: 求基准数(最小的,只有一个) 128-105=23 第五步: 求适合条件的数X X=23+105K(K是整数) 这个步骤让我想起了韩信点兵: 传说西汉大将韩信,由于比较年轻,开始他的部下对他不很佩服。有一次阅兵时,韩信要求士兵分三路纵队,结果末尾多2人,改成五路纵队,结果末尾多3人,再改成七路纵队,结果又余下2人,后来下级军官向他报告共有士兵2395人,韩信立即笑笑说不对(因2395除以3余数是1,不是2),由于已经知道士兵总人数在2300?/FONT2400之间,所以韩信根据23,128,233,------,每相邻两数的间隔是105,便立即说出实际人数应是2333人(因2333=128+20χ105+105,它除以3余2,除以5余3,除以7余2)。这样使下级军官十分敬佩,这 以上是韩信点兵的故事,就要确定K值了。 另外一种解法: 用枚举筛选法解 按除数3,7同余2,依次逐一枚举;随后用除以5余3,进行筛选,便可获解。 摘录条件 3......2 (基准数) ÷ 5……3 同余 2 7......2 (一)求3和7的最小公倍数[3,7] =21 (二)进行枚举筛选 (1)21+2=23 23÷5=4……3 由此可以过一题:pku1006 /JudgeOnline/problem?id=1006 题目大意: 人的身体,情感,智力的高峰低谷都由周期,分别是23天,28天和33天,现在给出身体,情感,智力的起始天,请计算由此天开始的第几天会达到三个方便的峰值,输出此峰值。 思路: 运用中国剩余定理解得基准数,次数再减去起始天D,再加上23,28,33的最小公倍数21252,其值就是答案。 代码:PKU1006 #includeiostream using namespace std; int main(){ int p,e,i,d,j,k,a=1,b=1,c=1; for(j=1;;j++){ if(23*28*j%33==1){ a=23*28*j; break; } } for(j=1;;j++){ if(28*33*j%23==1){ b
您可能关注的文档
- 董秘、证代必备的9本工具书.doc
- 白糖的制作工艺.ppt
- 菲德勒的权变领导理论.ppt
- 17.1.2勾股定理的应用1.ppt
- 高三复习:血糖调节.ppt
- 德尔菲法在护理研究中的应用.ppt
- 动能定理经典例题.ppt
- 勾股定理逆定理讲义(经典例题+详解+习题).doc
- 正弦定理-习题课课件.pptx
- 凯莱-哈密顿定理.ppt
- 2024年证券分析与咨询服务项目投资申请报告代可行性研究报告.docx
- 2024年铬酸酐项目资金申请报告代可行性研究报告.docx
- 2024年清洁胶项目资金申请报告代可行性研究报告.docx
- 2024年肉松饼项目投资申请报告代可行性研究报告.docx
- 2024年陆上泵项目资金需求报告代可行性研究报告.docx
- 2024年未硫化复合橡胶及其制品项目资金需求报告代可行性研究报告.docx
- 2024年精密温控节能设备项目资金筹措计划书代可行性研究报告.docx
- 2024年汽车覆盖件模具项目资金筹措计划书代可行性研究报告.docx
- 宋词行书钢笔字帖.pdf
- 我的暑假生活作文三年级300字10篇.pdf
最近下载
- 北师大版三年级下册数学《节约》教学设计(2课时).docx
- 2024年世界人口老龄化趋势.pptx
- 蛛网膜下腔出血查房课件.pptx
- 孤独症概述—认识孤独症儿童.pptx
- 任务三记述与动物相处 课件 2024-2025学年统编版语文七年级上册(2024).pptx VIP
- 洪步林氏脉络初.doc VIP
- 赣美版小学五年级上册美术教案全册.docx VIP
- 2023-2024学年北师大版(2019)必修第一册Unit 2 Sports and Fitness Writing Workshop 课件-.pptx
- sql必知必会清晰文字版.pdf
- 《9 作息有规律》教学设计-2024-2025学年道德与法治一年级上册统编版.docx VIP
文档评论(0)