1、中國剩余定理,擴展歐幾里德定理,1,看過射雕英雄傳的同學應該記得，當年黃蓉身中奇毒，郭靖將她送到瑛姑那里救治，進入瑛姑茅舍，瑛姑就給他們出了一題：“今有物不知其數(shù)，三三數(shù)之剩二；五五數(shù)之剩三：七七數(shù)之剩二。問物幾何？”黃蓉天資聰慧，哪里難得住她，她略微思考，答：23。大家是不是很好奇，黃蓉是怎么解出這道題的呢？,2,其實，這就是享譽中外的中國剩余定理。,一、剩余問題在整數(shù)除法里，一個數(shù)同時除以幾個數(shù)，整數(shù)商后，均有剩余；已知各除數(shù)及其對應的余數(shù)，從而要求出適合條件的這個被除數(shù)的問題，叫做剩余問題。,3,古代人的解法：,凡三三數(shù)之剩一，則置七十；五五數(shù)之剩一，則置二十一；七七數(shù)之剩一則置十五；一

2、百六以上，以一百零五減之即得。依定理譯成算式解為：702213152233233105223,4,一些關于中國剩余定理的定理：,定理1：幾個數(shù)相加，如果只有一個加數(shù)，不能被數(shù)a整除，而其他加數(shù)均能被數(shù)a整除，那么它們的和，就不能被數(shù)a整除。如：10能被5整除，15能被5整除，但7不能被5整除，所以（10+15+7）不能被5整除。,5,一些關于中國剩余定理的定理：,定理2：二數(shù)不能整除，若被除數(shù)擴大（或縮?。┝藥妆?，而除數(shù)不變，則其余數(shù)也同時擴大（或縮?。┫嗤谋稊?shù)（余數(shù)必小于除數(shù)）。如：22731（224）71214（4）（要余2即222762）（229）72819-7（2）（想余5則2257

3、155）,6,現(xiàn)在人的解法：,用各除數(shù)的“基礎數(shù)”法解。,7,基礎數(shù)的條件：,（1）此數(shù)必須符合除數(shù)自身的余數(shù)條件；（2）此數(shù)必須是其他所有各除數(shù)的公倍數(shù)。,8,第一步：求各除數(shù)的最小公倍數(shù)3，5，7105第二步：求各除數(shù)的基礎數(shù),9,（1）3105335353112（2）510552121541（當于3）13321363（3）710571515721（當于2）12215230,10,第三步：求各基礎數(shù)的和35+63+30128第四步：求基準數(shù)（最小的，只有一個）128-105=23第五步：求適合條件的數(shù)XX23+105K（K是整數(shù)）,11,這個步驟讓我想起了韓信點兵：,傳說西漢大將韓信，由于

4、比較年輕，開始他的部下對他不很佩服。有一次閱兵時，韓信要求士兵分三路縱隊，結果末尾多2人，改成五路縱隊，結果末尾多3人，再改成七路縱隊，結果又余下2人，后來下級軍官向他報告共有士兵2395人，韓信立即笑笑說不對（因2395除以3余數(shù)是1，不是2），由于已經(jīng)知道士兵總人數(shù)在2300?/FONT2400之間，所以韓信根據(jù)23，128，233，-，每相鄰兩數(shù)的間隔是105，便立即說出實際人數(shù)應是2333人（因2333=128+20105+105，它除以3余2，除以5余3，除以7余2）。這樣使下級軍官十分敬佩，這,12,以上是韓信點兵的故事，就要確定K值了。另外一種解法：用枚舉篩選法解按除數(shù)3，7同余

5、2，依次逐一枚舉；隨后用除以5余3，進行篩選，便可獲解。,13,摘錄條件3.2（基準數(shù)）53同余27.2（一）求3和7的最小公倍數(shù)3，721（二）進行枚舉篩選（1）212=2323543,14,由此可以過一題：pku1006,15,代碼：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=

6、1)c=23*33*j;break;j=0;printf(a=%dtb=%dtc=%dn,a,b,c);while(scanf(%d%d%d%d,16,改進版：PKU1006,#includeusingnamespacestd;intmain()inti,p,e,d,k,j=0;while(scanf(%d%d%d%d,17,Hdoj1730,18,Hdoj1573,19,Pku2891,20,代碼：PKU2891,#include#include_int64exGcd(_int64a,_int64b,_int64,21,PKU1061青蛙的約會,22,代碼：PKU1061,#includeu

7、singnamespacestd;_int64X,Y;_int64exp_gcd(_int64a,_int64b,_int64,23,模板：,基礎數(shù)：intextended_euclid(inta,intb,int,24,模板：,基準數(shù)：intchinese_remainder(intb,intw,intlen)inti,d,x,y,m,n,ret;ret=0;n=1;for(i=0;ilen;i+)n*=wi;for(i=0;ilen;i+)m=n/wi;d=extended_euclid(wi,m,x,y);ret=(ret+y*m*bi)%n;return(n+ret%n)%n;,25,模板：最大公約數(shù),intgcd(inta,intb)if(0=a)returnb;i