國際大學(xué)生程序設(shè)計競賽--數(shù)論與算法

1、國際大學(xué)生程序設(shè)計競賽－－數(shù)論與算法 主講：王樹林,數(shù)論基本知識,信息學(xué)中應(yīng)用的關(guān)于素數(shù)和整除的知識并不多，關(guān)鍵在于靈活應(yīng)用。素數(shù)和整除問題 如果a和b是整數(shù)，a≠0，若有整數(shù)c使b＝ac，就說a整除b。在a整除b時，記a是b的一個因子，b是a的倍數(shù)。用符號a∣b表示a整

2、除b，a不能整除b記為a ⊥b。 整除基本性質(zhì)有：（1）若a∣b， a∣c，則a∣（b＋c）（2）若a∣b，則對所有整數(shù)c， a∣bc（3）若a∣b， b∣c，則a∣c （傳遞性） 自反，反對稱，傳遞性，偏序關(guān)系。是一個格。素數(shù)（prime）和合數(shù)（compound），如果一個整數(shù)p只有1和p兩個因子，則p為素數(shù)，不為素數(shù)的其它數(shù)為合數(shù)。如果n為合數(shù)，則n必有一個小于或等于n的平方根的數(shù)因子。算術(shù)基本

3、定理：每個正整數(shù)都可以唯一地表示成素數(shù)的乘積。其中素數(shù)因子從小到大依次出現(xiàn)。,數(shù)論基本知識,除法的定義和同余 a＝dq＋r。同余：a≡b(mod c)最大公約數(shù)gcd(a,b)最小公倍數(shù)lcm(a,b)ab＝gcd(a,b)×lcm(a,b)如果gcd(a,b)=1,則a與b互素。,數(shù)論基本知識,1。如何求出1～n中的所有素數(shù)？ Eraosthenes氏篩法：每次求出一個新的素數(shù)，就把n以內(nèi)的它的所有倍數(shù)

4、都篩去。2。給出一個數(shù)n，如何判斷它是不是素數(shù)？ 1）樸素的判別法 從2開始試除小于n的所有自然數(shù)，時間復(fù)雜度為O(n). 2） 如果a是n的因子，那么n/a也是n的因子，所以如果n有一個大于1的真因子，則它必有一個不大于n1/2的因子，時間復(fù)雜度O(n1/2)。 等等。這些方法太慢。偽素數(shù)：如果n是一個正整數(shù)，并且存在和n互素的正整數(shù)a滿足an-1 ≡ 1(mod n), 我們說n是基于a的偽素數(shù)。如果一個數(shù)是

5、偽素數(shù)，它幾乎肯定是素數(shù)。另一方面，如果一個數(shù)不是偽素數(shù)，它一定不是素數(shù)。,數(shù)論基本知識,Miller-Rabbin測試 function Miller-Rabbin(n:longint):boolean; begin for i:=1 to s do Begin a:=random(n-2)+2; If modular_exp(a,n-1,n)1 then r

6、eturn false; end; End; return true; End; 這是一個概率型算法，屬于Monte-Carlo算法系列。 時間復(fù)雜度為O（s×log3n）。,最大公約數(shù)的求法,歐幾里德輾轉(zhuǎn)相除法function gcd(a,b:longint):longint;Begin if b=0 then gcd:=a; else gcd:=gcd(b,

7、 a mod b); End;,擴展的歐幾里德算法,如果（a，b）＝d，那么一定存在x，y滿足ax＋by＝d。Function 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 begi

8、n extended_gcd:=extended_gcd(b, a mod b); t:=x; x:=y; y:=t-(a div b) * y; end;End;,佳佳的困惑,題目：給出一個數(shù)N，含數(shù)字1，2，3，4，把N的所有數(shù)字重新排列一下組成一個新數(shù)，使它是7的倍數(shù)。分析：把數(shù)字1，2，3，4從中抽出，然后把其他數(shù)字按照原順序排列組成的自

9、然數(shù)w，w×10000整除7取余有7種可能，即是0，1，2，3，4，5，6。如果能把1，2，3，4排列出7個數(shù)，使它們整除7取余的值分別為0，1，2，3，4，5，6，把這4位數(shù)接在w后面即為問題的解。,除法表達式,題目：除法表達式有如下的形式：X1/X2/X3/…/Xk.其中Xi是正整數(shù)且X≤1000 000 000（1≤i≤k，k≤10 000）。除法表達式應(yīng)當(dāng)按照從左到右的順序計算。可以在表達式中嵌入順序?，F(xiàn)在給一個除法表

10、達式E要求告訴是否可以通過增加括號使表達式為E‘，E’是整數(shù)。分析： 顯然X1為分子，X2比為分母，其它數(shù)可以為分子也可以為分母。,方法一：將分母X2分解質(zhì)因數(shù)，由于X2≤1000000000，所以質(zhì)因數(shù)個數(shù)不超過29個。逐一掃描X1，X3，X4…，Xk，看能否將X2約掉。方法二：還是逐一掃描X1，X3，X4…，Xk，看能否將X2約掉，但不進行因數(shù)分解，而是每次約掉它和X2的最大公約數(shù)。,同余模算術(shù),同余：a≡b( mod

11、 c)性質(zhì)1：同余關(guān)系是一個等價關(guān)系。性質(zhì)2：a≡a1,b ≡b1(mod m),則a+b ≡a1+b1,a-b ≡a1-b1,ab ≡a1b1(mod m).性質(zhì)3：若ac ≡bd，c ≡d(mod m), 且(c,m)=1,則a ≡b( mod m).模m剩余等價類。和m互素的剩余等價類的個數(shù)記為f(m), 在和m互素的剩余類中各取一個代表元：a1,a2,a3,…,af(m).,它們組成m的一個縮剩余系。,關(guān)于f(m),有一

12、下性質(zhì)： 對于質(zhì)數(shù)p，f(p)=p-1,f(pn)=pn(p-1). 若(m,m’)=1,f(mm’)=f(m)f(m’).Euler定理 若(k,m)=1,則kf(m) ≡1(mod m)費馬小定理 對于素數(shù)p和任意整數(shù)a，有ap ≡a(mod p),反過來，滿足ap ≡a(mod p)，p也幾乎一定是素數(shù)。,求ax≡b(mod n)所有解的算法 利用歐幾里德輾轉(zhuǎn)相除法，模方程等

13、價于存在整數(shù)y，使得ax－ny＝b，時間復(fù)雜度為o（n＋logb）。Procedure modular_linear_equation(a,b,n:longint);Begin d:=extended_gcd(a,n,x,y); If b mod d 0 then no_answer; e:=x*(b div d) mod n; For i:=0 to d-1 do ans

14、[i+1]:=(e+i*n div d) mod n; End;,ACM實戰(zhàn)－－荒島野人 克里特島以野人群居而著稱。島上有排列成環(huán)行的M個山洞。這些山洞順時針編號為1，2，…M。島上住著n個野人，一開始依次住在山洞C1，C2,…,Cn中，以后每年，第i個野人會沿順時針向前走Pi個洞住下來。每個野人i有一個壽命值Li，即生存的年數(shù)。奇怪的是，雖然野人有很多，但沒有任何兩個野人在有生之年處在同一個山洞中，使得小島一直保持和平與

15、寧靜，這讓科學(xué)家們很驚奇。他們想知道，至少有多少個山洞，才能維持島上的和平呢？,分析,假設(shè)野人i的初始位置為Pi，每年跨越Si個山洞，壽命為Ti.很明顯，M≥Max{Pi, i∈[1..n]}.此題的核心問題是對于一個確定的M，如何求出任一對野人i和j（這里規(guī)定Si≥Sj）的最早相遇時間Age。如果相遇時間（不要求是最早相遇時間）為x，那么一定滿足等式： Pi＋Si*x ≡Pj＋Sj*x（mod M）.(Si-Sj)

16、*x ≡(Pj-Pi+M)(mod M)這是一個線性同余方程。如果方程無解，野人i和j永遠不會相遇；否則，可以求出所有解中的最小非負整數(shù)Age。只需枚舉從Max{Pi}到106枚舉山洞的個數(shù)M，對每一個M考慮是否任何兩個野人在有生之年不會在同一個山洞中，直到找到符合要求的M。,練習(xí)題,如果直角三角形三條邊長均為整數(shù)，這三個整數(shù)組成的數(shù)組就稱為勾股數(shù)組（a，b，c），根據(jù)定理有關(guān)系式a2+b2=c2有一種勾股數(shù)組（a，b，c），使得b