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

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

2/2/2023例題

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

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