中国剩余定理

中国剩余定理,扩展欧几里德定理,看过射雕英雄传的同学应该记得，当年黄蓉身中奇毒，郭靖将她送到瑛姑那里救治，进入瑛姑茅舍，瑛姑就给他们出了一题：“今有物不知其数，三三数之剩二；五五数之剩三：七七数之剩二。问物几何？”黄蓉天资聪慧，哪里难得住她，她略微思考，答：23。大家是不是很好奇，黄蓉是怎么解出这道题的呢？,其实，这就是享誉中外的中国剩余定理。,一、剩余问题在整数除法里，一个数同时除以几个数，整数商后，均有剩余；已知各除数及其对应的余数，从而要求出适合条件的这个被除数的问题，叫做剩余问题。,古代人的解法：,凡三三数之剩一，则置七十；五五数之剩一，则置二十一；七七数之剩一则置十五；一百六以上，以一百零五减之即得。依定理译成算式解为：702213152233233105223,一些关于中国剩余定理的定理：,定理1：几个数相加，如果只有一个加数，不能被数a整除，而其他加数均能被数a整除，那么它们的和，就不能被数a整除。如：10能被5整除，15能被5整除，但7不能被5整除，所以（10+15+7）不能被5整除。,一些关于中国剩余定理的定理：,定理2：二数不能整除，若被除数扩大（或缩小）了几倍，而除数不变，则其余数也同时扩大（或缩小）相同的倍数（余数必小于除数）。如：22731（224）71214（4）（要余2即222762）（229）72819-7（2）（想余5则2257155）,现在人的解法：,用各除数的“基础数”法解。,基础数的条件：,（1）此数必须符合除数自身的余数条件；（2）此数必须是其他所有各除数的公倍数。,第一步：求各除数的最小公倍数3，5，7105第二步：求各除数的基础数,（1）3105335353112（2）510552121541（当于3）13321363（3）710571515721（当于2）12215230,第三步：求各基础数的和35+63+30128第四步：求基准数（最小的，只有一个）128-105=23第五步：求适合条件的数XX23+105K（K是整数）,这个步骤让我想起了韩信点兵：,传说西汉大将韩信，由于比较年轻，开始他的部下对他不很佩服。有一次阅兵时，韩信要求士兵分三路纵队，结果末尾多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）。这样使下级军官十分敬佩，这,以上是韩信点兵的故事，就要确定K值了。另外一种解法：用枚举筛选法解按除数3，7同余2，依次逐一枚举；随后用除以5余3，进行筛选，便可获解。,摘录条件3.2（基准数）53同余27.2（一）求3和7的最小公倍数3，721（二）进行枚举筛选（1）212=2323543,由此可以过一题：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=%dtb=%dtc=%dn,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,i