數(shù)論和計算幾何

數(shù)論和計算幾何2/2/2023數(shù)論方面2/2/2023整除兩個整數(shù)a和b(a<>0)，如果存在一個整數(shù)c，滿足a*c=b，則稱為a整除b，符號記為a|b。2/2/2023mod運算給定一個正整數(shù)p，任意一個整數(shù)n，一定存在等式n=kp+r其中k、r是整數(shù)，且0≤r<p，稱呼k為n除以p的商，r為n除以p的余數(shù)。我們定義r為nmodp。2/2/2023mod運算的性質(zhì)(a+b)modc=((amodc)+(bmodc))modc(a-b)modc=((amodc)-(bmodc))modc(a*b)modc=((amodc)*(bmodc))modc注意：(a/b)modc的求法需要運用乘法逆元，有關(guān)資料可以上網(wǎng)查找，這里就不闡述了。2/2/2023素數(shù)與合數(shù)如果一個大于1的整數(shù)，其因數(shù)只有1和其本身，那么則稱這個整數(shù)為素數(shù)，否則為合數(shù)。1既不是素數(shù)也不是合數(shù)2/2/2023素數(shù)判斷若整數(shù)c是一個合數(shù)，則他必然有一個<=sqrt(n)的因子，因為若a是c的因子，必然存在因子b，使得a*b=c，而a和b若同時大于sqrt(c)，則a*b>c，不符合條件，所以上述結(jié)論成立。因此我們判斷一個數(shù)字n是否是素數(shù)，只需枚舉2到sqrt(n)中是否存在n的因子，不存在則為素數(shù)，存在的話則是合數(shù)。時間復(fù)雜度O(sqrt(n)).2/2/2023若一個數(shù)字p是合數(shù)，用上述作法也可以求出這個數(shù)字的約數(shù)個數(shù)和其約數(shù)具體是哪些數(shù)字。若數(shù)字a是數(shù)字p的約數(shù)(a<=sqrt(p))，則p/a也是其約數(shù)。2/2/2023篩法篩法是用來求不超過整數(shù)n(n>1)的所有質(zhì)數(shù)的一種方法。最常用的篩法是埃拉托斯特尼篩法，具體做法是：先把N個自然數(shù)按次序排列起來。1不是質(zhì)數(shù)，也不是合數(shù)，要劃去。第二個數(shù)2是質(zhì)數(shù)留下來，而把2后面所有能被2整除的數(shù)都劃去。2后面第一個沒劃去的數(shù)是3，把3留下，再把3后面所有能被3整除的數(shù)都劃去。3后面第一個沒劃去的數(shù)是5，把5留下，再把5后面所有能被5整除的數(shù)都劃去。這樣一直做下去，就會把不超過N的全部合數(shù)都篩掉，留下的就是不超過N的全部質(zhì)數(shù)。當(dāng)然還有其他的篩法，這里就不一一敘述了。2/2/2023算術(shù)基本定理任何一個大于1的自然數(shù)N，都可以唯一分解成有限個質(zhì)數(shù)的乘積N=(P1^a1)*(P2^a2)......(Pn^an),這里P1<P2<...<Pn是質(zhì)數(shù)，其諸方冪ai是正整數(shù)。2/2/2023質(zhì)因數(shù)分解我們可以從2到sqrt(n)枚舉整數(shù)n的質(zhì)因數(shù)，如果數(shù)字i滿足i|n，則i就是p的一個質(zhì)因子，這是我們將n/i。當(dāng)然n有可能包含多個i，所以還需要記錄出現(xiàn)了多少個i，然后依次枚舉下去。當(dāng)然這里不會出現(xiàn)枚舉的數(shù)字不是質(zhì)因子的情況，因為如果當(dāng)前枚舉的數(shù)字是合數(shù)p，則這個合數(shù)的質(zhì)因數(shù)在之前就已經(jīng)從n中剔除掉了，此時的n是無法被p整除的。2/2/2023若最后的n不為1，則此時的n也為原來的n的質(zhì)因子。因為一個整數(shù)N可以分解為有限個質(zhì)數(shù)的乘積N=(P1^a1)*(P2^a2)......(Pn^an)因此其約數(shù)個數(shù)除了之前提到的方法進行統(tǒng)計，還可以使用其分解質(zhì)數(shù)的個數(shù)，來進行統(tǒng)計F(N)=(1+a1)*(1+a2)*.....(1+an)2/2/2023例題N因子給你一個整數(shù)N(N<=20000),要求你求出至少包含N個因子的最小整數(shù)是多少？2/2/2023首先對于一個數(shù)求其約數(shù)個數(shù)之前我們有提到過兩種方法，這題我們?nèi)羰且粋€個數(shù)枚舉過去，找到一個最小的數(shù)字其約數(shù)個數(shù)>=N，那么用這兩種中哪一種方法求約數(shù)個數(shù)，很明顯都是要不可行的。2/2/2023但是利用第二種求約數(shù)總數(shù)的方法，我們可以設(shè)定一個約數(shù)總數(shù)M，求出一個包含M個約數(shù)的整數(shù)(但是不一定是最小的包含M個約數(shù)的整數(shù))。假設(shè)我們要求構(gòu)造一個有x個約數(shù)的數(shù)字y，那么我們可以將x進行分解x=a1*a2*...an因為y是由我們構(gòu)造的，因此y的質(zhì)因子可以隨便選取，為了使的y盡量小，我們可以從小到大選擇質(zhì)因子，同時使得a1>a2>a3...>an，新構(gòu)造的數(shù)字為y=2^(a1-1)*3^(a2-1)*5^(a3-1)*....*P^(an-1)2/2/2023具體實現(xiàn)我們可以用搜索，設(shè)一個搜索上界M，用前面所述的方法去枚舉每個質(zhì)因數(shù)的指數(shù)構(gòu)造不超過m的整數(shù)。如果有構(gòu)造數(shù)因子數(shù)超過了n并且比當(dāng)前答案要優(yōu)，那么更新答案。2/2/2023而上界我們也可以大致的進行一個估計，估計的數(shù)字為第1個素數(shù)到第log(20000)+1個素數(shù)的乘積，由前面分析的情況可以得知這是一個包含2^(log(20000)+1)個因子的數(shù)字，超過了數(shù)據(jù)的最大范圍。因此題目所要求的最小數(shù)字一定在這個數(shù)字的范圍之內(nèi)。2/2/2023例題給定正整數(shù)a與b，求a到b之間素數(shù)的個數(shù)。1<=a<=b<=1000000000b-a<=10000002/2/2023如果直接把a到b之間的數(shù)字一個個判斷它們是否是素數(shù)顯然是行不通的。如果直接用篩法篩出b以內(nèi)所有的素數(shù)，很顯然還是行不通的。那么對于這么大的數(shù)據(jù)，怎么做才能行得通呢？2/2/2023之前證明過一個整數(shù)n是合數(shù)的話在2到sqrt(n)以內(nèi)必然會有一個因子，而這個因子有可能是合數(shù)或者質(zhì)數(shù)，如果是合數(shù)的話那么很顯然這個合數(shù)因子可以拆分成更小的質(zhì)數(shù)因子，因此可以得出結(jié)論：整數(shù)n是合數(shù)的話在2到sqrt(n）以內(nèi)必然會有一個質(zhì)因子。有了這樣的結(jié)論，那么這題的思路就很明朗了。2/2/2023首先我們篩出1到sqrt(b)之內(nèi)所有的質(zhì)數(shù)，再用這些質(zhì)數(shù)去篩出a到b之內(nèi)的質(zhì)數(shù)，如果a到b之間的數(shù)字i沒有一個小于sqrt(b)的質(zhì)因子，那么他就是質(zhì)數(shù)，否則就是合數(shù)。這樣一來就可以算出答案了。2/2/2023GCD最大公約數(shù)(GCD)：設(shè)a和b為兩個不全為0的整數(shù)，能使c|a并且c|b的最大整數(shù)c，稱c為a與b的最大公約數(shù)2/2/2023求gcd的常用解法：輾轉(zhuǎn)相除法gcd(a,b)=gcd(b,amodb)證明：a可以表示成a=kb+r則r=amodb。假設(shè)d是a,b的一個公約數(shù)，則d|a,d|b，而r=a-kb，因此d|r。因此d也是（b,amodb）的公約數(shù)。因此（a,b）和（b,amodb）的公約數(shù)是一樣的，其最大公約數(shù)也必然相等，得證。時間復(fù)雜度O(logn)2/2/2023多個數(shù)的gcdgcd(a,b,c)=gcd(a,gcd(b,c))2/2/2023LCM最小公倍數(shù)(LCM):設(shè)a和b為兩個不全為0的整數(shù)，能使a|c并且b|c的最小整數(shù)c，稱c為a與b的最小公倍數(shù)a*b=gcd(a,b)*lcm(a,b)2/2/2023LCM的解法lcm(a,b)=a*b/gcd(a,b)多個數(shù)的LCMlcm(a,b,c)=a*b*c/gcd(a,b,c)2/2/2023例題1[noip2009]Hankson的趣味題n組數(shù)據(jù)每組數(shù)據(jù)給定正整數(shù)a0,a1,b0,b1，設(shè)某未知正整數(shù)為X，X滿足:1.X和a0的最大公約數(shù)是a1。2.X和b0的最小公倍數(shù)是b1。求滿足上述條件的正整數(shù)X的個數(shù)[數(shù)據(jù)范圍]n<=20001<=a0,a1,b0,b1<=20000000002/2/2023如果數(shù)據(jù)范圍很小，我們可以直接枚舉X，把X帶入條件1和條件2進行檢驗，可行的話就累加答案。這樣的枚舉可以進行優(yōu)化，我們把枚舉檢驗的對象變?yōu)閍1的倍數(shù)，因為a1是x和a0的最大公約數(shù)，所以a1的倍數(shù)自然有可能是x，但是由于數(shù)據(jù)范圍很大，這樣的方法不能使我們拿到全部的分?jǐn)?shù)2/2/2023我們從更細的地方進行思考，我們可以對最小公倍數(shù)和最大公約數(shù)進行分解質(zhì)因數(shù)后的指數(shù)進行分析。將A和B兩個整數(shù)進行分解質(zhì)因數(shù)A=p1^a1+p2^a2+p3^a3+......B=p1^b1+p2^b2+p3^a3+......這樣最小公倍數(shù)和最大公約數(shù)可表示為gcd(a,b)=p1^min(a1,b1)+p2^min(a2,b2)+p3^min(a3,b3)+.....lcm(a,b)=p1^max(a1,b1)+p2^max(a2,b2)+p3^max(a3,b3)+.....2/2/2023這樣我們可以先用篩法預(yù)處理出trunc(sqrt(2000000000))以內(nèi)全部的素數(shù)，用這些素數(shù)我們可以算出a0,a1,b0,b1每種質(zhì)數(shù)因子的個數(shù)t1,t2,t3,t4設(shè)我們要求的x的每種質(zhì)因數(shù)個數(shù)為S若數(shù)據(jù)合法，則t1>=t2,t3<=t4在數(shù)據(jù)合法的情況下，結(jié)合之前我們得出的最大公約數(shù)和最小公倍數(shù)質(zhì)因數(shù)分解后指數(shù)的關(guān)系，我們可以求出S的范圍1.若t1>t2，則s=t2，若t1=t2，則s>=t22.若t3<t4，則s=t4，若t3=t4，則s<=t4將1和2得到的s集合進行并集，如果為空集，則表示無解，直接輸出0，否則用乘法原理，將得出的s的個數(shù)乘進答案中。2/2/2023例題2設(shè)有兩個正整數(shù)集A和B，如果正整數(shù)n既是A中所有元素的公倍數(shù)，又是B中所有元素的公約數(shù)，則n為因子約數(shù)。請找出有多少個n。正整數(shù)集A有x個數(shù)，正整數(shù)集有y個數(shù)（1<=x,y<=50,1<=ai,bi<=1000000000)

2/2/2023和第一題其實差不多，我們分別求出正整數(shù)集A的最小公倍數(shù)X和正整數(shù)集B的最大公約數(shù)Y，因為可行的因子約數(shù)質(zhì)因數(shù)分解后的每個質(zhì)因數(shù)個數(shù)的范圍和X、Y有關(guān)，所以把X和Y進行質(zhì)因數(shù)分解，可以和上題一樣，對于某個質(zhì)因數(shù)pi，若x中所包含的pi個數(shù)與y中所包含的pi個數(shù)的交集為空集，則判定為無解，否則統(tǒng)計進答案中。2/2/2023互質(zhì)當(dāng)N個整數(shù)的最大公約數(shù)為1時，稱這N個數(shù)互質(zhì)。2/2/2023☆歐拉函數(shù)對正整數(shù)n，歐拉函數(shù)φ(n)是小于或等于n的正整數(shù)中與n互質(zhì)的數(shù)的數(shù)目。φ(x)=x(1-1/p1)(1-1/p2)(1-1/p3)(1-1/p4)…..(1-1/pn),其中p1,p2……pn為x的所有質(zhì)因數(shù)，x是不為0的整數(shù)。2/2/2023快速冪快速冪是用來快速計算a^nmodp的一種方法。如果n是偶數(shù)則a^n=a^(n/2)*a^(n/2)如果n是奇數(shù)則a^n=a^(n/2)*a^(n/2)*a如果在最后才進行modp可能會溢出，根據(jù)之前說的mod運算的性質(zhì)，我們在遞歸時可以邊做邊取模。2/2/2023同余兩個整數(shù)a,b，若它們除以正整數(shù)m所得的余數(shù)相等，則稱a，b對于模m同余記作a≡b(modm)2/2/2023擴展歐幾里得擴展歐幾里得算法可以求出方程ax+by=gcd(a,b)的一組解。在歐幾里得算法中，當(dāng)b=0時，此時a則為原a、b的最大公約數(shù)，此時滿足上面方程的解為x=1，y=0。通過遞歸，若已知bx'+(amodb)y'=gcd(a,b)的解x'和y'則gcd(a,b)=bx'+(amodb)y'=bx'+(a-[a/b]*b)y'=ay'+b*(x'-[a/b]*y')所以x=y',y=x'-[a/b]*y'由此可知ax+by=gcd(a,b)的解，不斷的向上回溯，最后得到結(jié)果

2/2/2023例題

【noip2012D2】同余方程求關(guān)于x的同余方程ax≡1(modb)的最小正整數(shù)解。數(shù)據(jù)保證一點有解。(2<=a,b<=2000000000)2/2/2023這里可以把方程轉(zhuǎn)換成axmodb=1，進而再轉(zhuǎn)化成ax+by=1。ax+by=1有解的充要條件為d=gcd(a,b)=1證明:(1)若ax+by=1有解則方程左邊必能被d整除，而右邊也需要能被d整除，因此d=1。(2)存在一系列正整數(shù)或負(fù)整數(shù)x使得ax+by=d=1結(jié)合上述兩點得證。2/2/2023這里求得的只是ax+by=1的一組解，而題目要求x需要是最小正整數(shù)。假設(shè)求出來的解是x0和y0，那么其余的解為x=x0+b*ty=y0-a*t由上式就可以求出ax≡1(modb)的最小正整數(shù)解。2/2/2023擴展歐幾里得最常見的用途就是解不定方程ax+by=c，當(dāng)然還有其他用途，但是在這里我就不深入闡述了，如果有感興趣的同學(xué)可以自己上網(wǎng)搜索相關(guān)資料。2/2/2023

計算幾何方面2/2/2023浮點誤差的處理因為計算機處理浮點數(shù)會有精度問題，比如正確的結(jié)果應(yīng)該為0，可是計算機計算出來的結(jié)果卻0.000000001，因此我們實現(xiàn)程序的時候應(yīng)該記得對誤差進行處理。2/2/2023具體程序funtionsgn(x:extended):integerbeginifabs(x)<=epsthensgn:=0elseifx>epsthensgn:=1elsesgn:=-1;end;2/2/2023向量與叉積向量：以(0,0)為起點到以(x,y)為終點的有向線段。叉積：向量A(x1,y1)和向量B(x2,y2)的叉積=x1y2-x2y1，即|A||B|sin(a,b)2/2/2023叉積有一個很重要的性質(zhì)，它可以通過符號來判斷兩向量間的順逆時針關(guān)系（定義順逆時針度數(shù)為180度內(nèi)）若P*Q>0,則P在Q順時針方向。若P*Q<0,則P在Q逆時針方向。若P*Q=0，則P與Q共線，但可能同向也有可能反向。2/2/2023叉積還有一個性質(zhì)，叉積會等于向量A、B作為鄰邊圍成的平行四邊形OACB的有向面積,要注意的是有向面積有正有負(fù)，我們將其取模后，即可得到平行四邊形OACB的面積。2/2/2023多邊形面積叉積可用于多邊形面積的作法，具體作法是把原點與多邊形的每個頂點連一條邊，然后依次求出多邊形相鄰兩個頂點與原點構(gòu)成的向量的叉積，取其總和后在取摸除以2就是該多邊形面積。2/2/2023例題POJ2318[TOY]一個矩形箱子，左上角與右下角的坐標(biāo)給出，里面有n塊板把箱子里的空間分隔成n+1個分區(qū)，給出這些板在上邊的x坐標(biāo)、下邊的x坐標(biāo)，以及m個玩具的坐標(biāo)，求這些分區(qū)里的玩具數(shù)目。n,m<=5000。2/2/2023首先我們可以把隔板從左到右進行排序。一個分區(qū)是由兩個隔板形成的，而判斷一個玩具是否在一個分區(qū)里面，我們可以一一枚舉兩個相鄰的隔板，運用之前說的叉積的性質(zhì)，來判斷點是否在分區(qū)內(nèi)。如果點在兩線段同側(cè)，則不在該分區(qū)內(nèi)，否則賊在分區(qū)內(nèi)。該算法時間復(fù)雜度O(n^2)，足以通過所有數(shù)據(jù)點，如果用二分來實現(xiàn)算法，可以優(yōu)化到O(nlogn)。2/2/2023線段位置關(guān)系我們可以通過判斷線段是否跨立和比較坐標(biāo)來判斷線段是否相交、重合或者分離。首先判斷是否互相跨立就是用叉積的性質(zhì)來判斷a和b是否在cd異側(cè)，c和d是否在ab異側(cè)。當(dāng)然通過上述的作法還不夠，因為如果上述作法得出的叉積都是0，那么說明兩線段共線，而共線的情況有分離相交和重合，這是我們可以比較坐標(biāo)的關(guān)系來求出線段的位置關(guān)系。2/2/2023凸包點集Q的凸包是指一個最小凸多邊形，滿足Q中的點或者在多邊形邊上或者在其內(nèi)。一組平面上的點，求一個包含所有點的最小的凸多邊形，這就是凸包問題。2/2/2023求解凸包的算法有好幾種，這里介紹一種最好理解的方法，其他方法各位同學(xué)感興趣的話可以上網(wǎng)搜索資料(Graham算法、快速凸包算法等),這里就不介紹了。這里介紹的算法名字叫做"卷包裹"算法。2/2/2023該算法可以這樣理解:在空地上樹立著一堆木樁，在一個最外側(cè)的木樁綁上一根很長繩子，然后順時針或者逆時針繞一圈。當(dāng)再一次回到這個起點木樁時，可以保證繩子正好卡主了所有外圍的木樁，并得到一個凸包。2/2/2023首先需要找到一個在凸包上的點，這里我們可以找最左邊的點，如果有多個點滿足條件，可以在這些滿足條件的點中選一個最下面的點。找到后加入凸包。然后以這個點為準(zhǔn)點，用向量的叉積找出除這個點以外最外側(cè)的點。并把這個點加入凸包。(如果有多個點滿足條件，如果需要保留凸包上的點，則在這些滿足條件的點中選一個最近的。若不保留，則選擇一個最遠的)。然后用這個新找到的點，在進行以上步驟。算法的終止條件就是找到的最外側(cè)點為最開始的起點。該算法的時間復(fù)雜度為O(NM)。N為點集中點的