中国剩余定理

中国剩余定理扩展欧几里德定理看过《射雕英雄传》的同学应该记得，当年黄蓉身中奇毒，郭靖将她送到瑛姑那里救治，进入瑛姑茅舍，瑛姑就给他们出了一题：“今有物不知其数，三三数之剩二；五五数之剩三：七七数之剩二。问物几何？”黄蓉天资聪慧，哪里难得住她，她略微思考，答：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＝321×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=2323÷5＝4……3由此可以过一题：pku1006=1006题目大意：人的身体，情感，智力的高峰低谷都由周期，分别是23天，28天和33天，现在给出身体，情感，智力的起始天，请计算由此天开始的第几天会达到三个方便的峰值，输出此峰值。思路：运用中国剩余定理解得基准数，次数再减去起始天D，再加上23，28，33的最小公倍数21252，其值就是答案。代码：PKU1006#includeiostreamusingnamespacestd;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,&p,&e,&i,&d)==4&&!(p==-1&&e==-1&&i==-1&&d==-1)){j++;k=(i*a+p*b+e*c-d+21252)%(23*28*33);if(k0)printf(Case%d:thenexttriplepeakoccursin%ddays.\n,j,k);elseprintf(Case%d:thenexttriplepeakoccursin21252days.\n,j);}return0;}改进版：PKU1006#includeiostreamusingnamespacestd;intmain(){inti,p,e,d,k,j=0;while(scanf(%d%d%d%d,&p,&e,&i,&d)&&!(p==-1&&i==-1&&e==-1&&d==-1)){j++;k=(p*5544+e*14421+i*1288-d+21252)%21252;if(k0)printf(Case%d:thenexttriplepeakoccursin%ddays.\n,j,k);elseprintf(Case%d:thenexttriplepeakoccursin21252days.\n,j);}return0;}Hdoj1730=1370跟PKU1006一样，只是要注意输入。scanf(%d,&x);while(x){getchar();x--;}Hdoj1573=1573求在小于等于N的正整数中有多少个X满足：Xmoda[0]=b[0],Xmoda[1]=b[1],Xmoda[2]=b[2],…,Xmoda[i]=b[i],…(0a[i]=10)。0N=1000,000,000Pku2891=2891大意：给出K对整数，每对整数假设是A和B，则一个数N，它除以A余B，求满足这K对整数的整数N。（直接用剩余定理）代码：PKU2891#includestdio.h#includestring.h__int64exGcd(__int64a,__int64b,__int64&x,__int64&y){__int64tmp,d;if(b==0){x=1;y=0;d=a;}else{d=exGcd(b,a%b,x,y);tmp=x;x=y;y=tmp-a/b*y;}returnd;}intmain(){__int64a1,m1,a2,m2,t,n,d,x,y;intflag;while(scanf(%I64d,&n)!=EOF){scanf(%I64d%I64d,&m1,&a1);n--;flag=0;while(n--){scanf(%I64d%I64d,&m2,&a2);d=exGcd(m1,m2,x,y);if((a2-a1)%d!=0)flag=1;t=m2/d;x*=(a2-a1)/d;x=(x%t+t)%t;a1=a1+m1*x;m1=(m1*m2)/d;a1=(a1%m1+m1)%m1;}if(flag)printf(-1\n);elseprintf(%I64d\n,a1);}return0;}PKU1061青蛙的约会=1061大意：青蛙A和青蛙B，规定纬度线上东经0度处为原点，一条首尾相接的数轴由东往西为正方向，单位长度1米。设青蛙A的出发点坐标是x，青蛙B的出发点坐标是y。青蛙A一次能跳m米，青蛙B一次能跳n米，两只青蛙跳一次所花费的时间相同。纬度线总长L米。现在要你求出它们跳了几次以后才会碰面。（同一时间跳到同一点上才算碰面）代码：PKU1061#includeiostreamusingnamespacestd;__int64X,Y;__int64exp_gcd(__int64a,__int64b,__int64&X,__int64&Y){__int64q,temp;if(b==0){q=a;X=1;Y=0;returnq;}else{q=exp_gcd(b,a%b,X,Y);temp=X;X=Y;Y=temp-(a/b)*Y;returnq;}}__int64GCD(__int64a,__int64b){__int64m=1;while(m){m=a%b；a=b;b=m;}returna;}__int64x,y,m,n,l,A,B,C;__int64gcd;intmain(){while(scanf(%I64d%I64d%I64d%I64d%I64d,&x,&y,&m,&n,&l)!=EOF){A=n-m;B=l;C=x-y;gcd=GCD(A,B);if(C%gcd!=0){printf(Impossible\n);continue;}A=A/gcd;B=B/gcd;C=C/gcd;exp_gcd(A,B,X,Y);X*=C;if(X0)X+=((-X/B)+1)*B;elseif(X0)X-=(X/B)*B;printf(%I64d\n,X);}}模板：基础数：intextended_euclid(inta,intb,int&x,int&y){intd;if(b==0){x=1;y=0;returna;}d=extended_euclid(b,a%b,y,x);y-=a/b*x;returnd;}模板：基准数：intchinese_remainder(intb[],intw[],intlen){inti,d,x,y,m,n,ret;ret=0;n=1;for(i=0;ilen;i++)n*=w[i];for(i=0;ilen;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)returnb;if(0==b)returna;if(ab){intm=a;a=b;b=m;}intc;for(c=a%b;c0;c=a%b){a=b;b=c;}returnb;}模板：最大公约数intgcd(inta,intb,int&ar,int&br){intx1,x2,x3;inty1,y2,y3;intt1,t2,t3;if(a==0){//有一个数为0,就不存在乘法逆元元ar=0;br=0;returnb;}if(b==0){ar=0;br=0;returna;}x1=1;x2=0;x3=a;y1=0;y2=1;y3=b;intk;for(t3=x3%y3;t3!=0;t3=x3%y3){k=x3/y3;t2=x2-k