acm中的數(shù)學問題數(shù)論部分省公開課一等獎全國示范課微課金獎課件

ACM中數(shù)學問題第一部分：數(shù)論主講人：錢明日期：Dec05,第1頁引言在ACM競賽中,經(jīng)常能夠看到數(shù)學問題身影能夠是純數(shù)學問題,也能夠是需要利用數(shù)學上一些公式,定理,算法來輔助處理問題會者不難,而不會選手在賽場上普通極難推出公式或進行證實往往想起來費勁,寫起來卻很輕松第2頁常見數(shù)學問題數(shù)論組合數(shù)學計算幾何博弈論線性代數(shù)高等數(shù)學線性規(guī)劃概率統(tǒng)計...第3頁本講內(nèi)容基本上是最基礎(chǔ),同時也是ACM競賽中最常見數(shù)學問題對一些數(shù)學公式,定理進行簡略地推導或證實,從而加深對它們了解和認識,也方便記憶往屆ACM競賽中數(shù)學問題第4頁數(shù)論簡而言之,數(shù)論就是研究整數(shù)理論在ACM競賽中,經(jīng)慣用到與數(shù)論相關(guān)知識純數(shù)論題目不多,大部分是和其它類型問題結(jié)合起來第5頁數(shù)論歷史自古以來,許許多多數(shù)學家研究過與數(shù)論相關(guān)問題直到十九世紀,數(shù)論才真正形成了一門獨立學科數(shù)論是一門高度抽象學科,長久處于純理論研究狀態(tài),曾經(jīng)被認為是極難有應用價值伴隨計算機科學發(fā)展,數(shù)論得到了廣泛應用第6頁數(shù)論主要內(nèi)容第一部分:同余相關(guān)整除性質(zhì)歐幾里德算法擴展歐幾里德算法中國剩下定理第二部分:素數(shù)相關(guān)算術(shù)基本定理歐拉定理素數(shù)測試Pollardrho方法第7頁數(shù)論主要內(nèi)容第一部分:同余相關(guān)整除性質(zhì)歐幾里德算法擴展歐幾里德算法中國剩下定理第二部分:素數(shù)相關(guān)算術(shù)基本定理歐拉定理素數(shù)測試Pollardrho方法第8頁第一部分同余相關(guān)整除基本性質(zhì)歐幾里德算法擴展歐幾里德算法中國剩下定理第9頁整除符號a|ba是b約數(shù)（因子），b是a倍數(shù)對于兩個不為0整數(shù)整除，被除數(shù)絕對值大于等于除數(shù)絕對值.對于正整數(shù)來講，a|b意味著b大，a小第10頁整除基本性質(zhì)性質(zhì)1：a|b,b|c=>a|c性質(zhì)2

：a|b=>a|bc性質(zhì)3

：

a|b,a|c=>a|kb±lc性質(zhì)4：

a|b,b|a=>a=±b第11頁整除基本性質(zhì)性質(zhì)5：a=kb±c=>a,b公因數(shù)與b,c公因數(shù)完全相同證實：假設(shè)d是b,c公因數(shù)，即d|b,d|c。利用整除性質(zhì)3，d整除b,c線性組合，故d|a。所以d是a,b公因數(shù)反之，假如d是a,b公因數(shù)，也能證出d是b,c公因數(shù)第12頁第一部分同余相關(guān)整除基本性質(zhì)歐幾里德算法擴展歐幾里德算法中國剩下定理第13頁請寫出12，30共有約數(shù)第14頁請寫出12，30共有約數(shù) 1,第15頁請寫出12，30共有約數(shù) 1,2,第16頁請寫出12，30共有約數(shù) 1,2,3,第17頁請寫出12，30共有約數(shù) 1,2,3,6.第18頁最大條約數(shù)與最小公倍數(shù)最大條約數(shù)定義：兩個或若干個整數(shù)條約數(shù)中最大那個條約數(shù)例子：12，30最大條約數(shù)怎樣求兩個整數(shù)最大條約數(shù)：輾轉(zhuǎn)相除法（擴展版）Stein算法第19頁請寫出12，10共有倍數(shù)第20頁請寫出12，10共有倍數(shù)60,第21頁請寫出12，10共有倍數(shù)60,120,第22頁請寫出12，10共有倍數(shù)60,120,180,第23頁請寫出12，10共有倍數(shù)60,120,180,240…第24頁最大條約數(shù)與最小公倍數(shù)最小公倍數(shù)定義：兩個或若干個整數(shù)共有倍數(shù)中最小那一個。例子：12，10最小公倍數(shù)最大條約數(shù)與最小公倍數(shù)關(guān)系lcm(a,b)*gcd(a,b)=a*b全部公倍數(shù)都是最小公倍數(shù)倍數(shù)，全部條約數(shù)都是最大條約數(shù)約數(shù)。第25頁歐幾里德算法歐幾里德算法(TheEuclideanAlgorithm)又稱輾轉(zhuǎn)相除法

或者短除法原理:gcd(a,b)=gcd(b,amodb)證實：利用整除性質(zhì)5(a=kb±c=>a,b公因數(shù)與b,c公因數(shù)完全相同)輾轉(zhuǎn)相除直到兩數(shù)整除，其中除數(shù)就是要求最大條約數(shù)。第26頁歐幾里德算法例子：利用歐幾里德算法，求63與81最大條約數(shù)步驟：a=81,b=63,amodb=18a←63,b←18,amodb=9a←18,b←9,amodb=0所以9就是63與81最大條約數(shù)第27頁歐幾里德算法歐幾里德算法:whileb>0

dor←a%ba←bb←rreturna第28頁歐幾里德算法歐幾里德算法是計算最大條約數(shù)傳統(tǒng)算法,也是最簡單算法,效率很高時間復雜度:O(lgn)(最壞情況:斐波那契數(shù)列相鄰兩項)空間復雜度:O(1)不過,對于大整數(shù)來說,取模運算非常耗時第29頁歐幾里德算法時間復雜度:最壞情況為斐波那契數(shù)列相鄰兩項體會(13,8)，(12,8)a=k*b+c,c=a-k*b同時滿足下面兩個條件，序列遞減得最慢，即輾轉(zhuǎn)相除法次數(shù)最多k=1最大條約數(shù)為1第30頁Stein算法原理:gcd(ka,kb)=k*gcd(a,b)當k=2時,說明兩個偶數(shù)最大條約數(shù)必定能被2整除當k與b互素時，gcd(ka,b)=gcd(a,b)當k=2時，說明計算一個偶數(shù)和一個奇數(shù)最大條約數(shù)時，能夠先將偶數(shù)除以2(a,b)=(b,a-b)第31頁Stein算法例子：兩個都為偶數(shù)(10,8)=2*(5,4)一個奇數(shù)，一個偶數(shù)(15,12)=

(15,6)兩個都是奇數(shù)(25,15)=(15,5)第32頁Stein算法Stein算法(假設(shè)0<=b<a):

r←0

whileb>0

doifa偶,b偶thena←a>>1b←b>>1r←r+1 elseifa偶,b奇thena←a>>1 elseifa奇,b偶thenb←b>>1 elseifa奇,b奇thena←(a-b)>>1

ifa<bthen交換a,b returna<<r第33頁Stein算法關(guān)鍵精華：兩個大數(shù)最大條約數(shù)轉(zhuǎn)化為兩個較小數(shù)最大條約數(shù)時間,空間復雜度均與歐幾里德算法相同最大優(yōu)點:只有移位和加減法計算,防止了大整數(shù)取模運算第34頁第一部分同余相關(guān)整除基本性質(zhì)歐幾里德算法擴展歐幾里德算法中國剩下定理第35頁擴展歐幾里德算法例子：利用歐幾里德算法，求63與81最大條約數(shù)第36頁擴展歐幾里德算法原理：對于不完全為0非負整數(shù)a，b，必定存在整數(shù)對x，y，使得gcd(a，b)=ax+by。a=kb+c,c=a–kb在用歐幾里德算法求解最大條約數(shù)過程中，將每一步余數(shù)都表示為原始兩個數(shù)線性組合形式。最大條約數(shù)就是歐幾里德算法中，最終不為0那個余數(shù)第37頁擴展歐幾里德算法擴展歐幾里德算法(遞歸實現(xiàn)):

intgcd(inta,intb) ifb=0 thenx←1y←0 returna d←gcd(b,a%b) x'←yy'←x-[a/b]y x←x'y←y' returnd第38頁擴展歐幾里德算法不但能求得最大條約數(shù)，還能求得關(guān)于原始兩個數(shù)線性組合。第39頁解二元模線性方程例子：解方程15x+12y=35x+4y=1(1,-1)解方程15x+12y=65x+4y=2(1,-1)*2解方程15x+12y=1gcd(15,12)=3，所以原方程無解第40頁解二元模線性方程二元模線性方程：形如ax≡c(modb)或ax+by=c其中a,b,c,x,y均為整數(shù)原理:令d=gcd(a,b),原方程有整數(shù)解當且僅當d|c擴展歐幾里德算法第41頁解二元模線性方程解二元模線性方程普通步驟約分到最簡形式找到初始解（擴展歐幾里德算法）加上或者減去兩個系數(shù)最小公倍數(shù)關(guān)于這兩個系數(shù)約數(shù)，也是這個方程解第42頁第一部分同余相關(guān)整除基本性質(zhì)歐幾里德算法擴展歐幾里德算法中國剩下定理第43頁中國剩下定理同模情況下，有這么性質(zhì)：乘法標準8mod7=1加法標準8mod7=110mod7=318mod7=416mod7=264mod7=8mod7第44頁中國剩下定理在0–14之間找到一個數(shù)，使得這個數(shù)除以3余1，除以5余2。經(jīng)求解該數(shù)為7，而且該數(shù)唯一。若不限定在0–14之間，那么這么數(shù)為7，22，37，52…兩個數(shù)之間相差3與5最小公倍數(shù)15第45頁中國剩下定理"物不知數(shù)"問題抽象表示:x≡2(mod3)x≡3(mod5)x≡2(mod7)求滿足上述條件最小正整數(shù)x第46頁中國剩下定理"物不知數(shù)"問題抽象表示:x≡2(mod3)x≡3(mod5)x≡2(mod7)求滿足上述條件最小正整數(shù)x“物不知數(shù)”問題標準解法:3k1+1,

5k2,7k3（70）3k1，5k2+1,7k3（21）3k1，5k2,7k3+1（15）x=70*2+21*3+15*2=233x=233–2*[3,5,7]=23第47頁中國剩下定理普通性問題:給定兩兩互質(zhì)正整數(shù)n1,n2,...,nk,要求找到最小正整數(shù)a,滿足a≡ai(modni)將問題分解成若干次求解二元模線性方程組解用擴展歐幾里德算法求解二元模線性方程第48頁中國剩下定理算法步驟:令n=n1n2...nk,mi=n/ni利用擴展歐幾里德算法計算出xi滿足mixi≡1(modni),因為n1,n2,...,nk兩兩互質(zhì),必有g(shù)cd(mi,ni)=1,即可確保一定有解則a≡a1x1m1+a2x2m2+...+akxkmk(modn)第49頁中國剩下定理經(jīng)典應用:大整數(shù)表示選取兩兩互素正整數(shù)n1,n2,...,nk求解對每個ni取模值ri,這個余數(shù)組就能夠唯一確定一個1~n1n2...nk大整數(shù)做大整數(shù)加,減,乘法時,只要確保在這個范圍內(nèi),均可轉(zhuǎn)化為分別對對應余數(shù)進行計算第50頁數(shù)論題目推薦2342、1528、1953(都是赤裸裸)進階題目：POJ1091、POJ1619、POJ1845、POJ2478、POJ2480、POJ2603、POJ2649、POJ2773、POJ2992、POJ3292第51頁第二部分素數(shù)相關(guān)算術(shù)基本定理歐拉定理素數(shù)測試Pollardrho方法第52頁關(guān)于互素性質(zhì)a與b,c同時互素，則a與b*c也互素p為素數(shù)，p|b*cp|borp|ca*b|cand(a,c)=1b|cak與b互素(k>=1)，則a與b也互素a≡1(modb)，則a與b互素第53頁篩法目標:求出n以內(nèi)全部質(zhì)數(shù)算法步驟:初始時容器內(nèi)為2到n全部正整數(shù)取出容器中最小數(shù)p,p一定是質(zhì)數(shù),刪去p全部倍數(shù)(注:只需從p2開始刪除即可)重復上述步驟直到容器為空第54頁篩法優(yōu)點:算法簡單,空間上只需要一個O(n)bool數(shù)組缺點:一個數(shù)可能被重復刪去屢次,影響效率例:在p=2,3,5,7時均會嘗試刪除210普通,若x有k個質(zhì)因子,則x會被處理k次第55頁篩法(改進)改進:初始時容器內(nèi)為2到n全部正整數(shù)取出容器中最小數(shù)p,p一定是質(zhì)數(shù)刪去全部pi,令q為第一個未被刪除數(shù),保留q,刪去全部piq,再令q為下一個未被刪除數(shù)...直到q遍歷全部未被刪除數(shù)為止(這一步驟能夠把最小質(zhì)因數(shù)為p全部數(shù)刪去)重復上面兩個步驟直到容器為空第56頁篩法(改進)用bool數(shù)組+雙向鏈表實現(xiàn),空間復雜度仍為O(n)小優(yōu)化:初始時只加入奇數(shù)第57頁算術(shù)基本定理任何一個大于1自然數(shù)n,都能夠唯一分解成有限個質(zhì)數(shù)乘積n=p1r1p2r2...pkrkp1<p2<...<pk均為質(zhì)數(shù),r1,r2,...rk均為正整數(shù)第58頁歐拉函數(shù)記φ(x)為與x互質(zhì)且小等于x正整數(shù)個數(shù)設(shè)x=p1r1p2r2...pkrkφ(x)=x*(1-1/p1)*(1-1/p2)*...*(1-1/pk)或φ(x)=p1(r1-1)(p1-1)p2(r2-1)(p2-1)...pk(rk-1)(pk-1)遞推形式:質(zhì)數(shù)p滿足p|x若p2|x,則φ(x)=φ(x/p)*p不然φ(x)=φ(x/p)*(p-1)第59頁歐拉函數(shù)證實:若p為質(zhì)數(shù),則φ(p)=p-1φ(pr)=pr(1-1/p)=p(r-1)(p-1)若a,b互質(zhì),則φ(ab)=φ(a)φ(b)擴展:n全部因子之和

(p10+...+p1r1)(p20+...+p2r2)...(pk0+...+pkrk)第60頁歐拉定理若a和m互質(zhì),則aφ(m)≡1(modm)證實:設(shè)φ(m)個正整數(shù)r1,r2,...,rφ(m)滿足:ri與m互質(zhì),對于任意i≠j,ri≠rj(modm)因為a與m互質(zhì),能夠證實ar1,ar2,...,arφ(m)依然滿足上述條件這么就有(ar1)(ar2)...(arφ(m))

≡r1r2...rφ(m)(modm)而(ar1)(ar2)...(arφ(m))

≡aφ(m)r1r2...rφ(m)(modm)兩邊同時約去r1r2...rφ(m)即得到歐拉定理第61頁素數(shù)測試費馬小定理:若p為素數(shù),則對于任意小于p正整數(shù)a,有a(p-1)≡1(modp)證實:歐拉定理特例(m為質(zhì)數(shù))問題:只是必要條件,不是充分條件反例:561,1105,1729...第62頁素數(shù)測試二次探測定理:若p為素數(shù),a2≡1(modp)小于p正整數(shù)解只有1和p-1滿足費馬小定理和二次探測定理數(shù)能夠確定是素數(shù)第63頁Miller-Rabin算法Miller-Rabin算法(n為待判定數(shù)):令n-1=m*2j,m為奇數(shù)隨機在2~(n-1)之間取一個整數(shù)b,令v=bm對v平方,當v=1時,若上一次v既不是1也不是(n-1),由二次探測定理,n不是素數(shù),退出