初等數(shù)論 (4)

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

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

3、cd(a,b),gcd(a,b)=gcd(b, a mod b) 程序：遞歸求解時間復(fù)雜度O(logb),,傳球游戲,N個人圍圈玩?zhèn)髑蛴螒颍_始時第一個人拿著球，每個人把球傳給左手的第K個人。滿足1≤K≤N/2。求K的最大值，使得第一個人重新拿到球之前，每個人都拿過球。輸入：數(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，接著試驗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。此時滿足題意的K就是N/2-1。N是偶數(shù)但不是4的倍數(shù)。此時N/2-1也是偶數(shù)，顯然不可能是正確答案。那么就來考察一下N/2-2：這是一個奇數(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。所以此時的答案就是N/2-2。,歐幾里得推廣,用一個線性組合來表示最大公約數(shù)，即d=gcd(a,b)=ax+by。要求計算出其中的整系數(shù)X和Y (X與Y可能為0或負(fù)數(shù)) 分析： 若b=0,則gcd(a,b)=a，x=1，y=0； 若b0,則首先計算出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’)。對應(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 //計算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ù)對（x,y）不是惟一的因為當(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á)式中嵌入括號以改變計算順序，例如表達(dá)式(1 / 2) / (1 / 2)的值為1。現(xiàn)在給一個除法表達(dá)式E要求告訴是否可以通過增加括號使表達(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，可按照下述方法計算x:⑴通過歐幾里得推廣算法求出d=gcd(a,n)和兩個滿足d=ax’+ny’的值x’和y’，表明X’是方程ax’≡d(mod n)的一個解。⑵若d不能被b整除，則方程ax≡b(mod n)沒有解;否則有d個解，其中第一個解的值為x0 = x’*(b/d) mod n,其余d-1個解可以通過對模n加上(n/d)的倍數(shù)來得到，即xi=(x0

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

12、，2，3每年要走過的洞穴數(shù)依次為3，7，2壽命值依次為4，3，1。,,分析,我們稱數(shù)字i每次順時針移動的格數(shù)pi為數(shù)字i的速度，初始位置ci為數(shù)字i的位置。數(shù)字i相對數(shù)字j的速度為pab[i，j]=，數(shù)字i相對數(shù)字j的位置為cab[i，j]。由于移動方向為順時針，因此相對位置cab[i，j]有方向之分，即若p[i]p[j]，cab[i，j]=c[j]-c[i]；具體計算如下：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}次移動中共同移動。它們能否在該期間相遇與空格數(shù)、相對位置cab[i，j]和的相對速度pab[i，j]有關(guān)。設(shè)x為移動次數(shù)，m為可能的空格數(shù)。顯然，若pab [i，j]*x

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

15、同余情況下的最小正整數(shù)x？令a=pab[i，j]，b=cab[i，j]為了計算a*x≡b(mod m)的最小正整數(shù)x，我們首先通過歐幾里德輾轉(zhuǎn)相除法計算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是保證成功移動的最少空格數(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 {枚舉每對數(shù)字的相對速度和相對位置} for j←i+1 to n do begin a←pab[i，j]；b←cab[i，j]； gcd(a，m，d，x，y)； {計算d=gcd(a，m)和滿足ax+m*y=d的x、y} if b mod d0 then continue；{若數(shù)字i和數(shù)字j不會相遇}

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

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

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

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

22、以數(shù)b所得的余數(shù),分析,分別寫出除數(shù)3、5、7的兩兩公倍數(shù).如下表：,答案為: (30+63+35) mod (7*3*5) = 23,規(guī)律,一個數(shù)除以3余2，除以5余3，除以7余2，求適合這個條件的最小數(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.  再用找到的三個較小數(shù)分別乘以被7、5、3除所得的余數(shù)的積連加，　　15×2+21×3+70×2=233.  最后用和233除以3、5、7三個除數(shù)的最小公倍數(shù).　　233÷105=2……余23，  這個余數(shù)23就是合乎條件的最小數(shù).  以上三個步驟適合于解類似“孫子問題”的所有問題.,總結(jié)規(guī)律,《孫子算經(jīng)》實際上是給出了下述一類

24、一次同余式組的解,中國剩余定理,考慮方程組x≡ai(mod mi), mi兩兩互素在0i時ei≡0(mod mj)則e1a1+e2a2+…+ekak就是一個解這個解加減 M的整數(shù)倍后就得到最小非負(fù)整數(shù)解,算法,Function china_system(k:integer):integer;//開始求M,隊每個i先求Mi,再求ei,把所有ei*ai累加起來.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,倉庫問題,倉庫中有n種貨物，貨物標(biāo)號為1

26、…n倉庫老板制訂了k套不同的貨物當(dāng)某套貨物刪除或更換某樣貨物后與另一套貨物相同時，認(rèn)為這兩套貨物是“類似”的。比如說貨物套“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”不類似。倉庫為m個商店服務(wù)，成套運輸貨物任意兩套“類似”的貨物不能送往同一個商店當(dāng)然可以不送任何貨物去某一家或多家商店請編