中国剩余定理ppt课件.ppt
中国剩余定理扩展欧几里德定理 l 看过射雕英雄传的同学应该记得，当年黄蓉身中奇毒，郭靖将她送到瑛姑那里救治，进入瑛姑茅舍，瑛姑就给他们出了一题：l “今有物不知其数，三三数之剩二；五五数之剩三：七七数之剩二。问物几何？”l 黄蓉天资聪慧，哪里难得住她，她略微思考，答：23。l大家是不是很好奇，黄蓉是怎么解出这道题的呢？其实，这就是享誉中外的中国剩余定理。 l一、剩余问题l 在整数除法里，一个数同时除以几个数，整数商后，均有剩余；已知各除数及其对应的余数，从而要求出适合条件的这个被除数的问题，叫做剩余问题。古代人的解法：l凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一则置十五；一百六以上，以一百零五减之即得。l依定理译成算式解为：l 702213152233l 233105223一些关于中国剩余定理的定理： l 定理1：几个数相加，如果只有一个加数，不能被数a整除，而其他加数均能被数a整除，那么它们的和，就不能被数a整除。l 如：10能被5整除，15能被5整除，但7不能被5整除，所以（10+15+7）不能被5整除。一些关于中国剩余定理的定理：l定理2：二数不能整除，若被除数扩大（或缩小）了几倍，而除数不变，则其余数也同时扩大（或缩小）相同的倍数（余数必小于除数）。 l如：22731l （224）71214（4）l （要余2即 222762）l （229）72819-7（2）l （想余5则2257155）现在人的解法：l用各除数的“基础数”法解。基础数的条件：l（1）此数必须符合除数自身的余数条件；l（2）此数必须是其他所有各除数的公倍数。l第一步：l求各除数的最小公倍数l 3，5，7105l第二步：l求各除数的基础数l （1）3 105335l 353112l （2）5 105 521l 21541（当于3）l 13321363l （3）7 105 715l 15 721（当于2）l 122l 15230l 第三步：l 求各基础数的和l 35+63+30128l 第四步：l 求基准数（最小的，只有一个）l 128-105=23l 第五步：l 求适合条件的数Xl X23+105K（K是整数）这个步骤让我想起了韩信点兵： l 传说西汉大将韩信，由于比较年轻，开始他的部下对他不很佩服。有一次阅兵时，韩信要求士兵分三路纵队，结果末尾多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）。这样使下级军官十分敬佩，这 l以上是韩信点兵的故事，就要确定K值了。l另外一种解法：l用枚举筛选法解l按除数3，7同余2，依次逐一枚举；随后用除以5余3，进行筛选，便可获解。l摘录条件l 3.2l（基准数） 53 同余 2l 7.2l（一）求3和7的最小公倍数3，7 21l（二）进行枚举筛选l （1）212=23 23543由此可以过一题：pku1006l http:/ 题目大意：l 人的身体，情感，智力的高峰低谷都由周期，分别是23天，28天和33天，现在给出身体，情感，智力的起始天，请计算由此天开始的第几天会达到三个方便的峰值，输出此峰值。l 思路：l 运用中国剩余定理解得基准数，次数再减去起始天D，再加上23，28，33的最小公倍数21252，其值就是答案。代码：PKU1006l#includelusing namespace std;lint main()lint p,e,i,d,j,k,a=1,b=1,c=1;lfor(j=1;j+)lif(23*28*j%33=1)la=23*28*j; break;lllfor(j=1;j+)lif(28*33*j%23=1)lb=28*33*j;lbreak;lllfor(j=1;j+)lif(23*33*j%28=1)lc=23*33*j;lbreak;lllj=0;lprintf(a=%dtb=%dtc=%dn,a,b,c);lwhile(scanf(%d%d%d%d,&p,&e,&i,&d)=4 & !(p=-1 & e=-1 & i=-1 & d=-1)lj+;lk=(i*a+p*b+e*c-d+21252)%(23*28*33);lif(k0)lprintf(Case %d: the next triple peak occurs in %d days.n,j,k);lelselprintf(Case %d: the next triple peak occurs in 21252 days.n,j);llreturn 0;l改进版：PKU1006l#includelusing namespace std;lint main()lint i,p,e,d,k,j=0;lwhile(scanf(%d%d%d%d,&p,&e,&i,&d) & !(p=-1 & i=-1 & e=-1 & d=-1)lj+;lk=(p*5544+e*14421+i*1288-d+21252)%21252;lif(k0)lprintf(Case %d: the next triple peak occurs in %d days.n,j,k);lelselprintf(Case %d: the next triple peak occurs in 21252 days.n,j);llreturn 0;lHdoj 1730l http:/ 跟PKU1006一样，只是要注意输入。l scanf(%d,&x);lwhile(x)llgetchar();lx-;lHdoj 1573lhttp:/ mod a0 = b0, X mod a1 = b1, X mod a2 = b2, , X mod ai = bi, (0 ai = 10)。l0 N = 1000,000,000 Pku 2891lhttp:/ _int64 exGcd (_int64 a, _int64 b, _int64 &x, _int64 &y)l_int64 tmp, d;lif (b = 0)l x = 1; y = 0; d = a;llelse l d = exGcd (b, a % b, x, y);l tmp = x; x = y; y = tmp - a / b * y;llreturn d;llint main ()l_int64 a1, m1, a2, m2, t, n, d, x, y;lint flag;lwhile (scanf (%I64d, &n) != EOF)l scanf (%I64d%I64d, &m1, &a1);l n-; flag = 0;l while (n-) l scanf (%I64d%I64d, &m2, &a2);l d = exGcd (m1, m2, x, y); l if (a2 - a1) % d != 0) flag = 1;l t = m2 / d;l x *= (a2-a1) / d;l x = (x % t + t) % t;l a1 = a1 + m1 * x;l m1 = (m1 * m2) / d;l a1 = (a1 % m1 + m1) % m1;l l if (flag) printf (-1n);l else printf (%I64dn, a1);llreturn 0;lPKU 1061 青蛙的约会青蛙的约会l http:/ 大意：青蛙A和青蛙B，规定纬度线上东经0度处为原点，一条首尾相接的数轴由东往西为正方向，单位长度1米。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。（同一时间跳到同一点上 才算碰面）代码：PKU1061l#include lusing namespace std;l_int64 X, Y;l_int64 exp_gcd(_int64 a, _int64 b, _int64 &X, _int64 &Y)l _int64 q, temp;l if(b = 0)l q = a; X = 1; Y = 0;l return q;l elsel q = exp_gcd(b, a % b, X, Y);l temp = X; X = Y; Y = temp - (a / b) * Y;l return q;l ll_int64 GCD(_int64 a, _int64 b)l _int64 m = 1;l while(m) l m = a%b； a = b; b = m;l l return a;ll_int64 x, y, m, n, l, A, B, C;l_int64 gcd; lint main()l while(scanf(%I64d%I64d%I64d%I64d%I64d, &x, &y, &m, &n, &l) != EOF) l A = n - m; B = l; C = x - y;l gcd = GCD(A, B);l if(C % gcd != 0) l printf(Impossiblen); continue;l l A = A/gcd; B = B/gcd; C = C/gcd;l exp_gcd(A, B, X, Y);l X *= C;l if(X 0) X -= (X/B)*B;l printf(%I64dn, X);l l模板：l 基础数：l int extended_euclid(int a, int b, int &x, int &y) l int d; l if(b = 0) x = 1; y = 0; return a; l d = extended_euclid(b, a % b, y, x); l y -= a / b * x; l return d; l 模板：l 基准数：l int chinese_remainder(int b, int w, int len) l int i, d, x, y, m, n, ret; l ret = 0; n = 1; l for(i=0; i len ;i+) n *= wi; l for(i=0; i b) l int m=a;a=b; b=m; l int c; l for(c = a % b ; c 0 ; c = a % b) l a = b; b = c; l return b; l 模板：最大公约数lint gcd(int a, int b , int& ar, int &br) lint x1,x2,x3; lint y1,y2,y3; lint t1,t2,t3; lif(a=0) /有一个数为0,就不存在乘法逆元元 l ar = 0; br=0; l return b; lif(b=0) lar=0; br=0; l return a; l x1= 1; x2= 0; x3=a; y1=0; y2=1; y3=b; lint k; l for( t3 = x3%y3 ; t3!=0; t3=x3% y3) lk = x3/y3; t2=x2- k*y2; t1=x1-k*y1; x1=y1; x1=y2; x3=y3; y1=t1; y2=t2; y3=t3; l if( y3 = 1) /有乘法逆元 l ar = y2; br=x1; return 1; lelse /公约数不为1，无乘法逆元 lar=0; br= 0; return y3; l
