中国剩余定理.ppt

中国剩余定理 扩展欧几里德定理 看过 射雕英雄传 的同学应该记得 当年黄蓉身中奇毒 郭靖将她送到瑛姑那里救治 进入瑛姑茅舍 瑛姑就给他们出了一题 今有物不知其数 三三数之剩二 五五数之剩三 七七数之剩二 问物几何 黄蓉天资聪慧 哪里难得住她 她略微思考 答 23 大家是不是很好奇 黄蓉是怎么解出这道题的呢 其实 这就是享誉中外的 中国剩余定理 一 剩余问题在整数除法里 一个数同时除以几个数 整数商后 均有剩余 已知各除数及其对应的余数 从而要求出适合条件的这个被除数的问题 叫做剩余问题 古代人的解法 凡三三数之剩一 则置七十 五五数之剩一 则置二十一 七七数之剩一则置十五 一百六以上 以一百零五减之即得 依定理译成算式解为 70 2 21 3 15 2 233233 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 2121 5 4 1 当于3 1 3 321 3 63 3 7 105 7 1515 7 2 1 当于2 1 2 2 15 2 30 第三步 求各基础数的和35 63 30 128第四步 求基准数 最小的 只有一个 128 105 23第五步 求适合条件的数XX 23 105K K是整数 这个步骤让我想起了韩信点兵 传说西汉大将韩信 由于比较年轻 开始他的部下对他不很佩服 有一次阅兵时 韩信要求士兵分三路纵队 结果末尾多2人 改成五路纵队 结果末尾多3人 再改成七路纵队 结果又余下2人 后来下级军官向他报告共有士兵2395人 韩信立即笑笑说不对 因2395除以3余数是1 不是2 由于已经知道士兵总人数在2300 FONT 2400之间 所以韩信根据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同余27 2 一 求3和7的最小公倍数 3 7 21 二 进行枚举筛选 1 21 2 2323 5 4 3 由此可以过一题 pku1006 代码 PKU1006 includeusingnamespacestd intmain intp 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 28 33 j break for j 1 j if 23 33 j 28 1 c 23 33 j break j 0 printf a d tb d tc d n a b c while scanf d d d d 改进版 PKU1006 includeusingnamespacestd intmain inti p e d k j 0 while scanf d d d d Hdoj1730 Hdoj1573 Pku2891 代码 PKU2891 include include int64exGcd int64a int64b int64 PKU1061青蛙的约会 代码 PKU1061 includeusingnamespacestd int64X Y int64exp gcd int64a int64b int64 模板 基础数 intextended euclid inta intb int 模板 基准数 intchinese remainder intb intw intlen inti d x y m n ret ret 0 n 1 for i 0 i len i n w i for i 0 i len i m n w i d extended euclid w i m x y ret ret y m b i n return n ret n n 模板 最大公约数 intgcd inta intb if 0 a retur