中国剩余定理幻灯片

1、中国剩余定理,扩展欧几里德定理,1,看过射雕英雄传的同学应该记得，当年黄蓉身中奇毒，郭靖将她送到瑛姑那里救治，进入瑛姑茅舍，瑛姑就给他们出了一题： “今有物不知其数，三三数之剩二；五五数之剩三：七七数之剩二。问物几何？” 黄蓉天资聪慧，哪里难得住她，她略微思考，答：23。 大家是不是很好奇，黄蓉是怎么解出这道题的呢？,2,其实，这就是享誉中外的中国剩余定理。,一、剩余问题 在整数除法里，一个数同时除以几个数，整数商后，均有剩余；已知各除数及其对应的余数，从而要求出适合条件的这个被除数的问题，叫做剩余问题。,3,古代人的解法：,凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一则置

2、十五；一百六以上，以一百零五减之即得。 依定理译成算式解为： 702213152233 233105223,4,一些关于中国剩余定理的定理：,定理1：几个数相加，如果只有一个加数，不能被数a整除，而其他加数均能被数a整除，那么它们的和，就不能被数a整除。 如：10能被5整除，15能被5整除，但7不能被5整除，所以（10+15+7）不能被5整除。,5,一些关于中国剩余定理的定理：,定理2：二数不能整除，若被除数扩大（或缩小）了几倍，而除数不变，则其余数也同时扩大（或缩小）相同的倍数（余数必小于除数）。 如：22731 （224）71214（4） （要余2即 222762） （229）72819-

3、7（2） （想余5则2257155）,6,现在人的解法：,用各除数的“基础数”法解。,7,基础数的条件：,（1）此数必须符合除数自身的余数条件； （2）此数必须是其他所有各除数的公倍数。,8,第一步： 求各除数的最小公倍数 3，5，7105 第二步： 求各除数的基础数,9,（1）3 105335 353112 （2）5 105 521 21541（当于3） 13321363 （3）7 105 715 15 721（当于2） 122 15230,10,第三步： 求各基础数的和 35+63+30128 第四步： 求基准数（最小的，只有一个） 128-105=23 第五步： 求适合条件的数X X23

4、+105K（K是整数）,11,这个步骤让我想起了韩信点兵：,传说西汉大将韩信，由于比较年轻，开始他的部下对他不很佩服。有一次阅兵时，韩信要求士兵分三路纵队，结果末尾多2人，改成五路纵队，结果末尾多3人，再改成七路纵队，结果又余下2人，后来下级军官向他报告共有士兵2395人，韩信立即笑笑说不对（因2395除以3余数是1，不是2），由于已经知道士兵总人数在2300?/FONT2400之间，所以韩信根据23，128，233，-，每相邻两数的间隔是105，便立即说出实际人数应是2333人（因2333=128+20105+105，它除以3余2，除以5余3，除以7余2）。这样使下级军官十分敬佩，这,12,

5、以上是韩信点兵的故事，就要确定K值了。 另外一种解法： 用枚举筛选法解 按除数3，7同余2，依次逐一枚举；随后用除以5余3，进行筛选，便可获解。,13,摘录条件 3.2 （基准数） 53 同余 2 7.2 （一）求3和7的最小公倍数3，7 21 （二）进行枚举筛选 （1）212=23 23543,14,由此可以过一题：pku1006, 题目大意： 人的身体，情感，智力的高峰低谷都由周期，分别是23天，28天和33天，现在给出身体，情感，智力的起始天，请计算由此天开始的第几天会达到三个方便的峰值，输出此峰值。 思路： 运用中国剩余定理解得基准数，次数再减去起始天D，再加上23，28，33的最小公

6、倍数21252，其值就是答案。,15,代码：PKU1006,#include 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=28*33*j; break; for(j=1;j+) if(23*33*j%28=1) c=23*33*j; break; j=0; printf(a=%dtb=%dtc=%dn,a,b,c); while(scanf(%d%d%d%d, ,

7、16,改进版：PKU1006,#include using namespace std; int main() int i,p,e,d,k,j=0; while(scanf(%d%d%d%d, ,17,Hdoj 1730, 跟PKU1006一样，只是要注意输入。 scanf(%d, ,18,Hdoj 1573, 求在小于等于N的正整数中有多少个X满足：X mod a0 = b0, X mod a1 = b1, X mod a2 = b2, , X mod ai = bi, (0 ai = 10)。 0 N = 1000,000,000,19,Pku 2891, 大意： 给出K对整数，每对整数假

8、设是A和B，则一个数N，它除以A余B，求满足这K对整数的整数N。 （直接用剩余定理）,20,代码：PKU2891,#include #include _int64 exGcd (_int64 a, _int64 b, _int64 ,21,PKU 1061 青蛙的约会, 大意：青蛙A和青蛙B，规定纬度线上东经0度处为原点，一条首尾相接的数轴由东往西为正方向，单位长度1米。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。（同一时间跳到同一点上 才算碰面）,22,代码：P

9、KU1061,#include using namespace std; _int64 X, Y; _int64 exp_gcd(_int64 a, _int64 b, _int64 ,23,模板：,基础数： int extended_euclid(int a, int b, int ,24,模板：,基准数： int chinese_remainder(int b, int w, int len) int i, d, x, y, m, n, ret; ret = 0; n = 1; for(i=0; i len ;i+) n *= wi; for(i=0; i len ;i+) m = n / wi; d = extended_euclid(wi, m, x, y); ret = (ret + y*m*bi) % n; return (n + ret%n) % n; ,25,模板：最大公约数,int gcd(int a,int b) if(0 = a )return