初等數(shù)論 (4)

1、初等數(shù)論,雅禮 朱全民,內(nèi)容介紹,素?cái)?shù)及其性質(zhì)歐幾里得公式gcd(a,b) 計(jì)算n的最大互質(zhì)數(shù)歐幾里得公式推廣：d=gcd(a,b)=ax+by計(jì)算同余方程 ax≡b(mod n)(n>0)求解同余式組a≡ai(mod ni）(1≤i≤k)計(jì)算不定方程ax+by=c數(shù)論的應(yīng)用,初等數(shù)論,基本概念整除和約數(shù)素?cái)?shù)和合數(shù)唯一分解定理除法的定義和同余最大公約數(shù)(gcd)和最小公倍數(shù)(lcm)互素、兩兩互素,素?cái)?shù)

2、測(cè)試,問(wèn)題一：求1~n的所有素?cái)?shù)Eraosthenes的篩子對(duì)于素?cái)?shù)p，刪除p*p, p*(p+1), p*(p+2)…例：求[n, n+m]內(nèi)的所有素?cái)?shù)n很大m很小如何篩？如何加速？,素?cái)?shù)測(cè)試,問(wèn)題二：給數(shù)n，它是素?cái)?shù)嗎？樸素算法：枚舉sqrt(n)內(nèi)約數(shù)改進(jìn)算法：枚舉sqrt(n)內(nèi)素?cái)?shù)預(yù)處理出sqrt(n)內(nèi)素?cái)?shù)：篩？Monte-Carlo算法不斷選基b，重復(fù)以下測(cè)試測(cè)試越多，正確概率越大,歐幾里得公式g

3、cd(a,b),gcd(a,b)=gcd(b, a mod b) 程序：遞歸求解時(shí)間復(fù)雜度O(logb),,傳球游戲,N個(gè)人圍圈玩?zhèn)髑蛴螒?，開始時(shí)第一個(gè)人拿著球，每個(gè)人把球傳給左手的第K個(gè)人。滿足1≤K≤N/2。求K的最大值，使得第一個(gè)人重新拿到球之前，每個(gè)人都拿過(guò)球。輸入：數(shù)串n（3 ≤ N ≤ 10200）輸出：K的最大值,,分析,如果n是奇數(shù)，那么最大的可能的[n/2]。由于k*2=n-1，所以gcd(k*2,n)=1，可

4、以得到gcd(k,n)=1，所以直接輸出[n/2]即可。如果N是偶數(shù)且為4的倍數(shù)：則N/2顯然不可能是符合要求的K，接著試驗(yàn)N/2-1，顯然有g(shù)cd(N/2-1, N/2)=1，而由于N是4的倍數(shù)，所以N/2是偶數(shù)，N/2-1是奇數(shù)，所以gcd(N/2-1, N)=1。此時(shí)滿足題意的K就是N/2-1。N是偶數(shù)但不是4的倍數(shù)。此時(shí)N/2-1也是偶數(shù)，顯然不可能是正確答案。那么就來(lái)考察一下N/2-2：這是一個(gè)奇數(shù)。根據(jù)剛才的介紹，有g(shù)c

5、d(N/2-2,N/2)≤2，但是N/2是奇數(shù)，所以gcd(N/2-2,N/2)=1。最后同樣可以得到gcd(N/2-2,N)=1。所以此時(shí)的答案就是N/2-2。,歐幾里得推廣,用一個(gè)線性組合來(lái)表示最大公約數(shù)，即d=gcd(a,b)=ax+by。要求計(jì)算出其中的整系數(shù)X和Y (X與Y可能為0或負(fù)數(shù)) 分析： 若b=0,則gcd(a,b)=a，x=1，y=0； 若b0,則首先計(jì)算出d’=gcd(b,a mod b)和滿足d’

6、=bx’+(a mod b)y’的x’、y’。在這種情況下, 有d=gcd(a,b)=d’=gcd(b,a mod b)。為了得到滿足d=ax+by的x和y，我們將d’=gcd(b,a mod b)轉(zhuǎn)化成線性組合d’=bx’+(a mod b)y’=bx’+(a-[a／b]b)y’ =ay’+b(x’-[a／b]y’)。對(duì)應(yīng)d=ax+by，選擇x=y’;y=x’-[a／b]*y’就可以滿足等式。,擴(kuò)展的Euclid算法,functio

7、n extended_gcd(a,b:longint; var x,y:longint):longint;begin if b=0 then begin extended_gcd:=a; x:=1; y:=0; end else begin //計(jì)算a與a mod b的最大公約數(shù)d’和滿足d’=ax’+a mod b*y’的x’、y’值。 //x=y’;y=x’-[a／b]*y

8、’ extended_gcd:=extended_gcd(b, a mod b, x, y); t:=x; x:=y; y:=t-(a div b)*y end;end; 滿足ax+by=d的數(shù)對(duì)（x,y）不是惟一的因?yàn)楫?dāng)x增加b，y減少a，和不變。,除法表達(dá)式,除法表達(dá)式有如下的形式：X1 / X2 / X3 / … / Xk其中Xi是正整數(shù)且Xi≤109 (1≤i≤k，k≤1

9、0 000)。除法表達(dá)式應(yīng)當(dāng)按照從左到右的順序求和，例如表達(dá)式1/2/1/2的值為1/4?？梢栽诒磉_(dá)式中嵌入括號(hào)以改變計(jì)算順序，例如表達(dá)式(1 / 2) / (1 / 2)的值為1?，F(xiàn)在給一個(gè)除法表達(dá)式E要求告訴是否可以通過(guò)增加括號(hào)使表達(dá)式值為E′，E′是整數(shù)。,分析,X2必須在分母其他都可以在分子最后結(jié)果是整數(shù)嗎？X2分解因數(shù)？復(fù)雜度？？？每次約掉X2和Xi的最大公約數(shù)！,線性同余方程ax≡b(mod n)(n&g

10、t;0),已知同余方程ax≡b(mod n)(n>0)中的a、b和n，可按照下述方法計(jì)算x:⑴通過(guò)歐幾里得推廣算法求出d=gcd(a,n)和兩個(gè)滿足d=ax’+ny’的值x’和y’，表明X’是方程ax’≡d(mod n)的一個(gè)解。⑵若d不能被b整除，則方程ax≡b(mod n)沒(méi)有解;否則有d個(gè)解，其中第一個(gè)解的值為x0 = x’*(b/d) mod n,其余d-1個(gè)解可以通過(guò)對(duì)模n加上(n/d)的倍數(shù)來(lái)得到，即xi=(x0

11、+i*(n/d))mod n (1≤i≤d-1),荒島野人,克里特島以野人群居而著稱。島上有排列成環(huán)行的M個(gè)山洞，順時(shí)針編號(hào)為1,2,…, M島上住著N個(gè)野人一開始依次住在山洞C1,C2,…, CN中以后每年，第i個(gè)野人會(huì)沿順時(shí)針向前走Pi個(gè)洞住下來(lái)每個(gè)野人i有一個(gè)壽命值Li，即生存的年數(shù)。至少有多少個(gè)山洞才能讓任何兩個(gè)野人在有生之年都不可能處在同一個(gè)山洞中,6個(gè)山洞，3個(gè)野人，前4年的情況3個(gè)野人初始的洞穴編號(hào)依次為1

12、，2，3每年要走過(guò)的洞穴數(shù)依次為3，7，2壽命值依次為4，3，1。,,分析,我們稱數(shù)字i每次順時(shí)針移動(dòng)的格數(shù)pi為數(shù)字i的速度，初始位置ci為數(shù)字i的位置。數(shù)字i相對(duì)數(shù)字j的速度為pab[i，j]=，數(shù)字i相對(duì)數(shù)字j的位置為cab[i，j]。由于移動(dòng)方向?yàn)轫槙r(shí)針，因此相對(duì)位置cab[i，j]有方向之分，即若p[i]p[j]，cab[i，j]=c[j]-c[i]；具體計(jì)算如下：for i←1 to n do for j←i+1

13、to n dobeginpab[i，j]←abs(p[i]-p[j])；cab[i，j]←c[j]-c[i]；if p[i]< p[j] then cab[i，j]←c[i]-c[j]；end；,分析,數(shù)字i和數(shù)字j在第1‥min{li，lj}次移動(dòng)中共同移動(dòng)。它們能否在該期間相遇與空格數(shù)、相對(duì)位置cab[i，j]和的相對(duì)速度pab[i，j]有關(guān)。設(shè)x為移動(dòng)次數(shù)，m為可能的空格數(shù)。顯然，若pab [i，j]*x

14、和cab [i，j]除以m有相同的余數(shù)，則說(shuō)明在第x次移動(dòng)中數(shù)字i和數(shù)字j處于同一個(gè)空格。我們的目的就是要尋找最小的m，使得任何一對(duì)數(shù)字在移動(dòng)過(guò)程中不會(huì)相遇，即x在（1‥min{l[i]，l[j]}）范圍內(nèi)，pab[i，j]*x≡cab[i，j](mod m)無(wú)解（1≤i≤n，i+1≤j≤n）。問(wèn)題轉(zhuǎn)化為給定空格數(shù)m，如何判斷pab[i，j]*x和cab[i，j] 除以m有相同的余數(shù)(1≤x≤min{l[i]，l[j]})，并且計(jì)算出

15、同余情況下的最小正整數(shù)x？令a=pab[i，j]，b=cab[i，j]為了計(jì)算a*x≡b(mod m)的最小正整數(shù)x，我們首先通過(guò)歐幾里德輾轉(zhuǎn)相除法計(jì)算a和m的最大公約數(shù)d和滿足ax+my=b的x、y。,求滿足ax+my=b的x、y,procedure gcd(a，m：longint； var d，x，y：longint)；var c，t：longint；begin c←a mod m； if c=0 then be

16、gin d←m；x←0；y←1； end {then} else begin 　gcd(m，c，d，x，y)；t←x； x←y； y←t-a div m*y； end；{else}end；{ gcd },function check(m:longint)：boolean；{若m是保證成功移動(dòng)的最少空格數(shù)，則返回true；否則返回false}var i，j，mm，a，b，d，x，y，ans：l

17、ongint；begin check←false； for i←1 to n do {枚舉每對(duì)數(shù)字的相對(duì)速度和相對(duì)位置} for j←i+1 to n do begin a←pab[i，j]；b←cab[i，j]； gcd(a，m，d，x，y)； {計(jì)算d=gcd(a，m)和滿足ax+m*y=d的x、y} if b mod d0 then continue；{若數(shù)字i和數(shù)字j不會(huì)相遇}

18、 a←a div d；mm←m div d； b←b div d； gcd(a，mm，d，x，y)；{計(jì)算=1的x、y} ans←x*b；{ 因?yàn)樵匠炭s小了b倍，因此，移動(dòng)次數(shù)需要擴(kuò)大b倍} while ans=mm do ans←ans-mm； if(ans≤l[i])and(ans≤l[j])then exit；{經(jīng)ans次移動(dòng)后數(shù)字i和數(shù)字j相遇，則返回} end；{

19、for} check←true；{若在空格數(shù)為m的情況下所有數(shù)字無(wú)法相遇,則返回true}end；{ check },分析,如果b不能被d整除（b mod d≠0），則說(shuō)明數(shù)字i和數(shù)字j不會(huì)相遇；如果b能被d整除（b mod d=0），則計(jì)算*x’+*y’=1的x’、 y’，那么，x’*b+)mod即為滿足a*x≡b(mod m)的最小正整數(shù)x。如果數(shù)字i和數(shù)字j相遇的時(shí)間x大于min{ l[i]，l[j]}，則說(shuō)明這一對(duì)數(shù)字在共

20、同移動(dòng)的過(guò)程中不會(huì)相遇。若所有可能的數(shù)字對(duì)都滿足上述條件，則確定m是保證成功移動(dòng)的最少空格數(shù)。顯然，所有數(shù)字能夠成功移動(dòng)的空格數(shù)m至少是+1，上限是106。我們按照遞增順序枚舉m。若m代入check函數(shù)后返回ture，則m為最少可能的洞穴數(shù)。 由于歐幾里得輾轉(zhuǎn)相除法的時(shí)間復(fù)雜度可以近似地看成常數(shù)，所以算法的時(shí)間復(fù)雜度為O(m*n2),物不知數(shù),南北朝時(shí)期的數(shù)學(xué)著作《孫子算經(jīng)》中的“物不知數(shù)”題目 今有一些物不知其數(shù)量。如果三個(gè)三個(gè)

21、地去數(shù)它，則最后還剩二個(gè)；如果五個(gè)五個(gè)地去數(shù)它，則最后還剩三個(gè)；如果七個(gè)七個(gè)地去數(shù)它，則最后也剩二個(gè)。問(wèn)：這些物一共有多少？”用簡(jiǎn)練的數(shù)學(xué)語(yǔ)言來(lái)表述就是：求這樣一個(gè)數(shù)，使它被３除余２，被５除余３，被７除余２。,經(jīng)驗(yàn),經(jīng)驗(yàn)1:如果整數(shù)a除以整數(shù)b所得余數(shù)是1，那么，整數(shù)a的2倍、3倍、4倍、……、（b-1）倍除以整數(shù)b所得的余數(shù)就分別是2..b-1經(jīng)驗(yàn)2:連從某數(shù)a中續(xù)減去若干個(gè)b后，求所得的要求小于數(shù)b的差數(shù)，實(shí)際上就是求數(shù)a除

22、以數(shù)b所得的余數(shù),分析,分別寫出除數(shù)3、5、7的兩兩公倍數(shù).如下表：,答案為: (30+63+35) mod (7*3*5) = 23,規(guī)律,一個(gè)數(shù)除以3余2，除以5余3，除以7余2，求適合這個(gè)條件的最小數(shù).孫子的解法是：  先從3和5、3和7、5和7的公倍數(shù)中相應(yīng)地找出分別被7、5、3除均余1的較小數(shù)15、21、70.即　　15÷7=2……余1，　　21÷5=4……余1，　　70÷3

23、=23……余1.  再用找到的三個(gè)較小數(shù)分別乘以被7、5、3除所得的余數(shù)的積連加，　　15×2+21×3+70×2=233.  最后用和233除以3、5、7三個(gè)除數(shù)的最小公倍數(shù).　　233÷105=2……余23，  這個(gè)余數(shù)23就是合乎條件的最小數(shù).  以上三個(gè)步驟適合于解類似“孫子問(wèn)題”的所有問(wèn)題.,總結(jié)規(guī)律,《孫子算經(jīng)》實(shí)際上是給出了下述一類

24、一次同余式組的解,中國(guó)剩余定理,考慮方程組x≡ai(mod mi), mi兩兩互素在0i時(shí)ei≡0(mod mj)則e1a1+e2a2+…+ekak就是一個(gè)解這個(gè)解加減 M的整數(shù)倍后就得到最小非負(fù)整數(shù)解,算法,Function china_system(k:integer):integer;//開始求M,隊(duì)每個(gè)i先求Mi,再求ei,把所有ei*ai累加起來(lái).begin M:=1; for i:=1 to k do M:

25、=M*m(i); ans:=0 for i:=1 to k do begin mi:=M div m[i]; extended_gcd(Mi,m[i],pi,qi] ans:= (ans+Mi*pi*a[i]) mod M end; if ans<0 then ans:=ans+M; //求最小非負(fù)整數(shù)解 China_system:=ans;end,倉(cāng)庫(kù)問(wèn)題,倉(cāng)庫(kù)中有n種貨物，貨物標(biāo)號(hào)為1

26、…n倉(cāng)庫(kù)老板制訂了k套不同的貨物當(dāng)某套貨物刪除或更換某樣貨物后與另一套貨物相同時(shí)，認(rèn)為這兩套貨物是“類似”的。比如說(shuō)貨物套“1 2 3 4”就貨物套“3 2 1”、“1 2 5 3 4”、“1 2 3 4 2”和“1 5 4 3”類似，而和貨物套“1 2”、“1 1 2 2 3 4”和“4 5 3 6”不類似。倉(cāng)庫(kù)為m個(gè)商店服務(wù)，成套運(yùn)輸貨物任意兩套“類似”的貨物不能送往同一個(gè)商店當(dāng)然可以不送任何貨物去某一家或多家商店請(qǐng)編