第八講 ACM數(shù)論問(wèn)題.ppt

1、ACM數(shù)論問(wèn)題,工大ACM團(tuán)隊(duì),數(shù)論基本知識(shí),信息學(xué)競(jìng)賽和程序設(shè)計(jì)競(jìng)賽中常考的數(shù)論知識(shí)關(guān)于素?cái)?shù)和整 除，關(guān)鍵在于靈活應(yīng)用 整除:如果a和b是整數(shù)，a0，若有整數(shù)c使bac，就說(shuō)a整除b。在a整除b時(shí)，記a是b的一個(gè)因子，b是a的倍數(shù)。用符號(hào)ab表示a整除b，a不能整除b記為a b。 整除基本性質(zhì)有： （1）若ab， ac，則a（bc） （2）若ab，則對(duì)所有整數(shù)c， abc （3）若ab， bc，則ac （傳遞性）,工大ACM團(tuán)隊(duì),數(shù)論基本知識(shí),素?cái)?shù)（prime）和合數(shù)（compound），如果一個(gè)整數(shù)p只有1和p兩個(gè)因子，則p為素?cái)?shù)，不為素?cái)?shù)的其它數(shù)為合數(shù)。如果n為合數(shù)，則n必有一個(gè)小于或等

2、于n的平方根的數(shù)因子。 給出一個(gè)數(shù)n，如何判斷它是不是素?cái)?shù)？ 樸素的判別法 從2開(kāi)始試除小于n的所有自然數(shù)，時(shí)間復(fù)雜度為O(n). 如果a是n的因子，那么n/a也是n的因子，所以如果n有一個(gè)大于1的真因子，則它必有一個(gè)不大于n1/2的因子，時(shí)間復(fù)雜度O(n1/2)。 算術(shù)基本定理：每個(gè)正整數(shù)都可以唯一地表示成素?cái)?shù)的乘積。其中素?cái)?shù)因子從小到大依次出現(xiàn)。 最大公約數(shù)gcd(a, b) 最小公倍數(shù)lcm(a, b) abgcd(a, b)lcm(a, b) 如果gcd(a, b)=1，則a與b互素。,工大ACM團(tuán)隊(duì),素?cái)?shù)算法,最一般的求解n以內(nèi)素?cái)?shù)的算法。復(fù)雜度是o(n*sqrt(n)，適合n很小

3、num = 0; for(i=2; isqrt(i) ) primenum+ = i; ,工大ACM團(tuán)隊(duì),素?cái)?shù),當(dāng)n很大的時(shí)候，比如n=10,000,000時(shí)，n*sqrt(n)30,000,000,000,數(shù)量級(jí)相當(dāng)大 思考如何改進(jìn)？,工大ACM團(tuán)隊(duì),素?cái)?shù)篩法,最簡(jiǎn)單的素?cái)?shù)篩法 開(kāi)一個(gè)大的bool型數(shù)組prime，大小就是n+1就可以了.先把所有的下標(biāo)為奇數(shù)的標(biāo)為true,下標(biāo)為偶數(shù)的標(biāo)為false. 把奇數(shù)的倍數(shù)設(shè)為false. 見(jiàn)代碼-prime_choice.c 改進(jìn)的素?cái)?shù)篩法 bool型數(shù)組里面只存奇數(shù)不存偶數(shù)。如定義primeN,則0表示3，1表示5，2表示7，3表示9.。如果pr

4、ime0為true,則表示3時(shí)素?cái)?shù)。prime3為false意味著9是合數(shù)，每個(gè)單元代表的數(shù)是2*i+3。 欲求n以內(nèi)的素?cái)?shù)，就先把sqrt(n)內(nèi)的素?cái)?shù)求出來(lái)，用已經(jīng)求得的素?cái)?shù)來(lái)篩出后面的合數(shù)。,工大ACM團(tuán)隊(duì),數(shù)論基本知識(shí),如何求出1n中的所有素?cái)?shù)？ Eraosthenes（愛(ài)拉托斯尼篩法）篩法：每次求出一個(gè)新的素?cái)?shù)，就把n以內(nèi)的它的所有倍數(shù)都篩去。,經(jīng)典的Eraosthenes篩法：for (int i = 2; i * i N; i+)if (tagi) continue;for (int j = i; i * j N; j+) tagi*j = 1;for (int i = 2; i

5、 N; i+)if (!tagi) primetol+ = i;,一種線性篩素?cái)?shù)的方法（復(fù)雜度是O(n)）：void get_prime() int cnt = 0;for (int i = 2; i N; i+) if (!tagi) pcnt+ = i;for (int j = 0; j cnt /可以用均攤分析的方法來(lái)分析算法的復(fù)雜度,由于每 個(gè)合數(shù)都唯一的被它的最小素因子篩一次，而每個(gè)合 數(shù)的最小素因子都是唯一的，總復(fù)雜度是O(n),Eraosthenes篩法的速度并不快，原因在于對(duì)于一個(gè)合數(shù)，這種方法會(huì)重復(fù)的標(biāo)記,工大ACM團(tuán)隊(duì),偽素?cái)?shù),同余：ab(mod m) 如果兩個(gè)數(shù)a和b之差

6、能被m整除，那么我們就說(shuō)a和b對(duì)模數(shù)m同余。比如，100-60除以8正好除盡，我們就說(shuō)100和60對(duì)于模數(shù)8同余。它的另一層含義就是說(shuō)，100和60除以8的余數(shù)相同。a和b對(duì)m同余，我們記作ab(mod m)。比如，剛才的例子可以寫(xiě)成10060(mod 8)。你會(huì)發(fā)現(xiàn)這種記號(hào)到處都在用，比如和數(shù)論相關(guān)的書(shū)中就經(jīng)常把a(bǔ) mod 3 = 1寫(xiě)作a1(mod 3)。,工大ACM團(tuán)隊(duì),偽素?cái)?shù),同余：ab(mod m) 如果兩個(gè)數(shù)a和b之差能被m整除，那么我們就說(shuō)a和b對(duì)模數(shù)m同余。比如，100-60除以8正好除盡，我們就說(shuō)100和60對(duì)于模數(shù)8同余。它的另一層含義就是說(shuō)，100和60除以8的余數(shù)相同。

7、a和b對(duì)m同余，我們記作ab(mod m)。比如，剛才的例子可以寫(xiě)成10060(mod 8)。你會(huì)發(fā)現(xiàn)這種記號(hào)到處都在用，比如和數(shù)論相關(guān)的書(shū)中就經(jīng)常把a(bǔ) mod 3 = 1寫(xiě)作a1(mod 3)。 偽素?cái)?shù)：它滿足費(fèi)馬小定理，但其本身卻不是素?cái)?shù)。最小的偽素?cái)?shù)是341。事實(shí)上，費(fèi)馬小定理給出的是關(guān)于素?cái)?shù)判定的必要非充分條件。若n能整除2(n-1)-1，并n是非偶數(shù)的合數(shù)，那么n就是偽素?cái)?shù)。第一個(gè)偽素?cái)?shù)341 是薩魯斯在1819年發(fā)現(xiàn)的。 費(fèi)馬爾小定理：若n是素?cái)?shù)，且a0 則an-11(mod n) 或 an-1 mod n =1 即 (an-1-1)/n=0 2(5-1)-1=15,15|5. 2

8、(3-1)-1=3,3|3.但很多都是素?cái)?shù)，如3，5，7，29，31 1819年數(shù)學(xué)家薩魯斯找到了反例：2(341-1)-1|341,而341=11*31是合數(shù)，341就成了第一個(gè)偽素?cái)?shù)。以后又發(fā)現(xiàn)了許多偽素?cái)?shù)：561 645 1105 1387 1729,工大ACM團(tuán)隊(duì),偽素?cái)?shù),偽素?cái)?shù)的一個(gè)用途 利用偽素?cái)?shù)表來(lái)判定一個(gè)奇數(shù)n是否為素?cái)?shù)。 如果n不能整除2(n-1)1，則據(jù)費(fèi)馬小定理知，n必為合數(shù)； 如果n能整除2(n-1)1 ，且n在偽素?cái)?shù)表中，則n為合數(shù)，否則為素?cái)?shù)。 這種方法的關(guān)鍵就在于按偽素?cái)?shù)表去掉偽素?cái)?shù)，而這要求偽素?cái)?shù)在能整除2(n-1)1的數(shù)中相當(dāng)少才行，這就是當(dāng)n整除2(n-1)

9、1時(shí)，n是合數(shù)的比例問(wèn)題。 在前10億個(gè)自然數(shù)中，共有50847534個(gè)素?cái)?shù)，而只有以2為底的偽素?cái)?shù)5597個(gè)，即在此范圍內(nèi)n整除2n-11產(chǎn)生合數(shù)的可能性只有0.011%。在10億之內(nèi)，n整除2(n-1)1同時(shí)整除3(n-1)1 的合數(shù)n只有1272個(gè)，即此時(shí)產(chǎn)生合數(shù)的可能性只有0.0025%。,工大ACM團(tuán)隊(duì),Miller-Rabbin測(cè)試,如果n是一個(gè)正整數(shù)，如果存在和n互素的正整數(shù)a滿足an-11(mod n)，我們說(shuō)n是基于a的偽素?cái)?shù)。如果一個(gè)數(shù)是偽素?cái)?shù)，它幾乎肯定是素?cái)?shù)。 function Miller-Rabbin(n:longint):boolean; begin for i:

10、=1 to s do Begin a:=random(n-2)+2; If modular_exp(a,n-1,n)1 then return false; end; End; return true; End;,工大ACM團(tuán)隊(duì),大數(shù)的素性判斷,對(duì)于大數(shù)的素性判斷，目前Miller-Rabin算法應(yīng)用最廣泛。 一般底數(shù)仍然是隨機(jī)選取，但當(dāng)待測(cè)數(shù)不太大時(shí)，選擇測(cè)試底數(shù)就有一些技巧了。 比如，如果被測(cè)數(shù)小于4 759 123 141，那么只需要測(cè)試三個(gè)底數(shù)2, 7和61就足夠了。當(dāng)然，你測(cè)試的越多，正確的范圍肯定也越大。 如果你每次都用前7個(gè)素?cái)?shù)(2, 3, 5, 7, 11, 13和17)進(jìn)行測(cè)

11、試，所有不超過(guò)341 550 071 728 320的數(shù)都是正確的。 如果選用2, 3, 7, 61和24251作為底數(shù)，那么1016內(nèi)唯一的強(qiáng)偽素?cái)?shù)為46 856 248 255 981。 這樣的一些結(jié)論使得Miller-Rabin算法在OI(信息學(xué)奧林匹克競(jìng)賽 )中非常實(shí)用。通常認(rèn)為，Miller-Rabin素性測(cè)試的正確率可以令人接受，隨機(jī)選取 k個(gè)底數(shù)進(jìn)行測(cè)試算法的失誤率大概為4(-k)。 偽素?cái)?shù)：如果n是一個(gè)正整數(shù)，并且存在和n互素的正整數(shù)a滿足an-1 1(mod n), 我們說(shuō)n是基于a的偽素?cái)?shù)。如果一個(gè)數(shù)是偽素?cái)?shù)，它幾乎肯定是素?cái)?shù)。另一方面，如果一個(gè)數(shù)不是偽素?cái)?shù)，它一定不是素?cái)?shù)

12、。,工大ACM團(tuán)隊(duì),HDOJ_1108 最小公倍數(shù),給定兩個(gè)正整數(shù)，計(jì)算這兩個(gè)數(shù)的最小公倍數(shù)。 10 14 70,工大ACM團(tuán)隊(duì),歐幾里德算法,int gcd(int da,int xiao) int temp; while (xiao!=0) temp=da%xiao; da=xiao; xiao=temp; return(da); ,思考： 遞歸的形式如何寫(xiě)？,工大ACM團(tuán)隊(duì),擴(kuò)展的歐幾里德算法,對(duì)于不完全為 0 的非負(fù)整數(shù) a，b，gcd（a，b）表示 a，b 的最大公約數(shù)，必然存在整數(shù)對(duì) x，y ，使得 gcd（a，b）=ax+by。如果gcd(a, b)d，那么一定存在x，y滿足ax

13、byd。 擴(kuò)展歐幾里得算法其實(shí)是解二元一次不定方程的算法, 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 begin extended_gcd:=extended_gcd(b, a mod b); t:=x; x:=y; y:=t-(a div b) * y; end; End;,工大ACM團(tuán)隊(duì),擴(kuò)展的歐幾里德算法,求解 x，y的方法的理解 設(shè) ab。 1，顯然當(dāng) b=0，gcd（a，b）=a。此

14、時(shí) x=1，y=0； 2，ab0 時(shí) 設(shè) ax1+by1=gcd(a,b); bx2+(a mod b)y2=gcd(b,a mod b); 根據(jù)樸素的歐幾里德原理有 gcd(a,b)=gcd(b,a mod b); 則:ax1+by1=bx2+(a mod b)y2; 即:ax1+by1=bx2+(a-(a/b)*b)y2=ay2+bx2-(a/b)*by2; 根據(jù)恒等定理得：x1=y2; y1=x2-(a/b)*y2; 這樣我們就得到了求解 x1,y1 的方法：x1，y1 的值基于 x2，y2.,工大ACM團(tuán)隊(duì),擴(kuò)展的歐幾里德算法,int exGcd(int a, int b, int ,

15、工大ACM團(tuán)隊(duì),擴(kuò)展的歐幾里德算法的應(yīng)用,POJ 1061-青蛙的約會(huì) 兩只青蛙在網(wǎng)上相識(shí)了，它們聊得很開(kāi)心，于是覺(jué)得很有必要見(jiàn)一面。它們很高興地發(fā)現(xiàn)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止?？墒撬鼈兂霭l(fā)之前忘記了一件很重要的事情，既沒(méi)有問(wèn)清楚對(duì)方的特征，也沒(méi)有約定見(jiàn)面的具體位置。不過(guò)青蛙們都是很樂(lè)觀的，它們覺(jué)得只要一直朝著某個(gè)方向跳下去，總能碰到對(duì)方的。但是除非這兩只青蛙在同一時(shí)間跳到同一點(diǎn)上，不然是永遠(yuǎn)都不可能碰面的。為了幫助這兩只樂(lè)觀的青蛙，你被要求寫(xiě)一個(gè)程序來(lái)判斷這兩只青蛙是否能夠碰面，會(huì)在什么時(shí)候碰面。 我們把這兩只青蛙分別叫做青蛙A和青蛙B，并且規(guī)定緯度線上東經(jīng)

16、0度處為原點(diǎn)，由東往西為正方向，單位長(zhǎng)度1米，這樣我們就得到了一條首尾相接的數(shù)軸。設(shè)青蛙A的出發(fā)點(diǎn)坐標(biāo)是x，青蛙B的出發(fā)點(diǎn)坐標(biāo)是y。青蛙A一次能跳m米，青蛙B一次能跳n米，兩只青蛙跳一次所花費(fèi)的時(shí)間相同。緯度線總長(zhǎng)L米?，F(xiàn)在要你求出它們跳了幾次以后才會(huì)碰面。,工大ACM團(tuán)隊(duì),POJ 1061,輸入只包括一行5個(gè)整數(shù)x，y，m，n，L，其中xy 2000000000，0 m、n 2000000000，0 L 2100000000。 輸出碰面所需要的跳躍次數(shù)，如果永遠(yuǎn)不可能碰面則輸出一行Impossible,工大ACM團(tuán)隊(duì),POJ 1061,Input 輸入只包括一行5個(gè)整數(shù)x，y，m，n，L，其

17、中xy 2000000000，0 m、n 2000000000，0 L 2100000000。 Output 輸出碰面所需要的跳躍次數(shù)，如果永遠(yuǎn)不可能碰面則輸出一行Impossible Sample Input 1 2 3 4 5 Sample Output 4,工大ACM團(tuán)隊(duì),解題思路,此題其實(shí)就是擴(kuò)展歐幾里德算法求解不定方程，線性同余方程。 設(shè)過(guò)s步后兩青蛙相遇，則必滿足以下等式： (x+m*s)-(y+n*s)=k*l(k=0,1,2.) 稍微變一下形得： (n-m)*s+k*l=x-y 令n-m=a,k=b,x-y=c,即 a*s+b*l=c 只要上式存在整數(shù)解，則兩青蛙能相遇，否則不

18、能。 首先想到的一個(gè)方法是用兩次for循環(huán)來(lái)枚舉s,l的值，看是否存在s,l的整數(shù)解，若存在則輸入最小的s，但顯然這種方法是不可取的，誰(shuí)也不知道最小的s是多大，如果最小的s很大的話，超時(shí)是明顯的。,工大ACM團(tuán)隊(duì),解題思路,求a * x + b * y = n的整數(shù)解。 1、先計(jì)算Gcd(a,b)，若n不能被Gcd(a,b)整除，則方程無(wú)整數(shù)解；否則，在方程兩邊同時(shí)除以Gcd(a,b)，得到新的不定方程a * x + b * y = n，此時(shí)Gcd(a,b)=1; 2、利用上面所說(shuō)的歐幾里德算法求出方程a * x + b * y = 1的一組整數(shù)解x0,y0，則n * x0,n * y0是方程a * x + b * y = n的一組整數(shù)解； 3、根據(jù)數(shù)論中的相關(guān)定理，可得方程a * x + b * y = n的所有整數(shù)解為： x = n * x0 + b * t y = n * y0 - a * t (t為整數(shù)) 上面的解也就是a * x + b * y = n 的全部整數(shù)解。,工大ACM團(tuán)隊(duì),解題思路,此時(shí)方程的所有解為：x=c*k1