03-acm數(shù)論問題 (1)

1、ACM數(shù)論問題,,工大ACM團(tuán)隊(duì),數(shù)論基本知識(shí),信息學(xué)競賽和程序設(shè)計(jì)競賽中?？嫉臄?shù)論知識(shí)關(guān)于素?cái)?shù)和整除，關(guān)鍵在于靈活應(yīng)用整除:如果a和b是整數(shù)，a≠0，若有整數(shù)c使b＝ac，就說a整除b。在a整除b時(shí)，記a是b的一個(gè)因子，b是a的倍數(shù)。用符號(hào)a∣b表示a整除b，a不能整除b記為a ⊥b。整除基本性質(zhì)有：（1）若a∣b， a∣c，則a∣（b＋c）（2）若a∣b，則對(duì)所有整數(shù)c， a∣bc（3）若a∣b， b∣c，則a∣c

2、（傳遞性）,工大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è)小于或等于n的平方根的數(shù)因子。給出一個(gè)數(shù)n，如何判斷它是不是素?cái)?shù)？樸素的判別法 從2開始試除小于n的所有自然數(shù)，時(shí)間復(fù)雜度為O(n).如果a是n的因子，那么n/a也是n的因子，所以如果n有一個(gè)大于1的真因子，則它必有一個(gè)不大于n1/2的因子，時(shí)間復(fù)雜

3、度O(n1/2)。算術(shù)基本定理：每個(gè)正整數(shù)都可以唯一地表示成素?cái)?shù)的乘積。其中素?cái)?shù)因子從小到大依次出現(xiàn)。最大公約數(shù)gcd(a, b)最小公倍數(shù)lcm(a, b)ab＝gcd(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很小num = 0; for(i=2; isqrt(i) )

4、 prime[num++] = 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ù)篩法,最簡單的素?cái)?shù)篩法開一個(gè)大的bool型數(shù)組prime[]，大小就是n+1就可以了.先把所有的下標(biāo)為奇數(shù)的標(biāo)為true,下

5、標(biāo)為偶數(shù)的標(biāo)為false.把奇數(shù)的倍數(shù)設(shè)為false. 見代碼-prime_choice.c改進(jìn)的素?cái)?shù)篩法bool型數(shù)組里面只存奇數(shù)不存偶數(shù)。如定義prime[N],則0表示3，1表示5，2表示7，3表示9...。如果prime[0]為true,則表示3時(shí)素?cái)?shù)。prime[3]為false意味著9是合數(shù)，每個(gè)單元代表的數(shù)是2*i+3。欲求n以內(nèi)的素?cái)?shù)，就先把sqrt(n)內(nèi)的素?cái)?shù)求出來，用已經(jīng)求得的素?cái)?shù)來篩出后面的合數(shù)。,,,

6、工大ACM團(tuán)隊(duì),數(shù)論基本知識(shí),如何求出1～n中的所有素?cái)?shù)？ Eraosthenes（愛拉托斯尼篩法）篩法：每次求出一個(gè)新的素?cái)?shù)，就把n以內(nèi)的它的所有倍數(shù)都篩去。,經(jīng)典的Eraosthenes篩法：for (int i = 2; i * i < N; i++){    if (tag[i]) continue;    for (int j

7、= i; i * j < N; j++)         tag[i*j] = 1;}for (int i = 2; i < N; i++)    if (!tag[i])         prime[tol++] =

8、 i;,一種線性篩素?cái)?shù)的方法（復(fù)雜度是O(n)）：void get_prime(){  int cnt = 0;    for (int i = 2; i < N; i++)     {        if (!tag[i])  &#

9、160;  p[cnt++] = i;        for (int j = 0; j < cnt && p[j] * i < N; j++)         {      

10、       tag[i*p[j]] = 1;            if (i % p[j] == 0)            

11、60;break;         }     }}//可以用均攤分析的方法來分析算法的復(fù)雜度,由于每個(gè)合數(shù)都唯一的被它的最小素因子篩一次，而每個(gè)合數(shù)的最小素因子都是唯一的，總復(fù)雜度是O(n),Eraosthenes篩法的速度并不快，原因在于對(duì)于一個(gè)合數(shù)，這種方法會(huì)重復(fù)的標(biāo)記,工大ACM團(tuán)隊(duì),偽素?cái)?shù),同余：a

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

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

14、但其本身卻不是素?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-1≡1(mod n) 或 an-1 mod n =1 即 (an-1-1)/n=02^(5-1)-1=15,15|5. 2^(3-1)-1=3,3|3.但很多都是素?cái)?shù)，如3，5，7

15、，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ù)表來判定一個(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ù)。

16、這種方法的關(guān)鍵就在于按偽素?cái)?shù)表去掉偽素?cái)?shù)，而這要求偽素?cái)?shù)在能整除2^(n-1)－1的數(shù)中相當(dāng)少才行，這就是當(dāng)n整除2^(n-1)－1時(shí)，n是合數(shù)的比例問題。在前10億個(gè)自然數(shù)中，共有50847534個(gè)素?cái)?shù)，而只有以2為底的偽素?cái)?shù)5597個(gè)，即在此范圍內(nèi)n整除2n-1－1產(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%。,

17、工大ACM團(tuán)隊(duì),Miller-Rabbin測試,如果n是一個(gè)正整數(shù)，如果存在和n互素的正整數(shù)a滿足a^n-1≡1(mod n)，我們說n是基于a的偽素?cái)?shù)。如果一個(gè)數(shù)是偽素?cái)?shù)，它幾乎肯定是素?cái)?shù)。function Miller-Rabbin(n:longint):boolean; begin for i:=1 to s do Begin a:=random(n-2)+2;

18、 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)待測數(shù)不太大時(shí)，選擇測試底數(shù)就有一些技巧了。比如，如果被測數(shù)小于4 759 123 141

19、，那么只需要測試三個(gè)底數(shù)2, 7和61就足夠了。當(dāng)然，你測試的越多，正確的范圍肯定也越大。如果你每次都用前7個(gè)素?cái)?shù)(2, 3, 5, 7, 11, 13和17)進(jìn)行測試，所有不超過341 550 071 728 320的數(shù)都是正確的。如果選用2, 3, 7, 61和24251作為底數(shù)，那么10^16內(nèi)唯一的強(qiáng)偽素?cái)?shù)為46 856 248 255 981。這樣的一些結(jié)論使得Miller-Rabin算法在OI(信息學(xué)奧林匹克競賽 )中

20、非常實(shí)用。通常認(rèn)為，Miller-Rabin素性測試的正確率可以令人接受，隨機(jī)選取 k個(gè)底數(shù)進(jìn)行測試算法的失誤率大概為4^(-k)。偽素?cái)?shù)：如果n是一個(gè)正整數(shù)，并且存在和n互素的正整數(shù)a滿足an-1 ≡ 1(mod n), 我們說n是基于a的偽素?cái)?shù)。如果一個(gè)數(shù)是偽素?cái)?shù)，它幾乎肯定是素?cái)?shù)。另一方面，如果一個(gè)數(shù)不是偽素?cái)?shù)，它一定不是素?cái)?shù)。,工大ACM團(tuán)隊(duì),HDOJ_1108  最小公倍數(shù),給定兩個(gè)正整數(shù)，計(jì)算這兩個(gè)數(shù)的最小公倍

21、數(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);},思考：遞歸的形式如何寫？,工大ACM團(tuán)隊(duì),擴(kuò)展的歐幾里德算法,對(duì)于不完全為 0 的

22、非負(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＋by＝d。擴(kuò)展歐幾里得算法其實(shí)是解二元一次不定方程的算法, Function extended_gcd(a,b:longint; Var x,y:longint):longint;Begin if b=0 then begin

23、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的方法

24、的理解　　設(shè) a>b。 　　1，顯然當(dāng) b=0，gcd（a，b）=a。此時(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)

25、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 &x, int &y) { 　　if(b == 0) 　　{ 　　x = 1; 　　y = 0; 　　return a; 　　

26、} 　　int r = exGcd(b, a % b, x, y); 　　int t = x; 　　x = y; 　　y = t - a / b * y; },工大ACM團(tuán)隊(duì),擴(kuò)展的歐幾里德算法的應(yīng)用,POJ 1061---青蛙的約會(huì) 兩只青蛙在網(wǎng)上相識(shí)了，它們聊得很開心，于是覺得很有必要見一面。它們很高興地發(fā)現(xiàn)它們住在同一條緯度線上，于是它們約定各自朝西跳，直到碰面為止。可是它們出發(fā)之前忘記了一件很重要的事情，既沒有問清

27、楚對(duì)方的特征，也沒有約定見面的具體位置。不過青蛙們都是很樂觀的，它們覺得只要一直朝著某個(gè)方向跳下去，總能碰到對(duì)方的。但是除非這兩只青蛙在同一時(shí)間跳到同一點(diǎn)上，不然是永遠(yuǎn)都不可能碰面的。為了幫助這兩只樂觀的青蛙，你被要求寫一個(gè)程序來判斷這兩只青蛙是否能夠碰面，會(huì)在什么時(shí)候碰面。 我們把這兩只青蛙分別叫做青蛙A和青蛙B，并且規(guī)定緯度線上東經(jīng)0度處為原點(diǎn)，由東往西為正方向，單位長度1米，這樣我們就得到了一條首尾相接的數(shù)軸。設(shè)青蛙A的出發(fā)點(diǎn)坐

28、標(biāo)是x，青蛙B的出發(fā)點(diǎn)坐標(biāo)是y。青蛙A一次能跳m米，青蛙B一次能跳n米，兩只青蛙跳一次所花費(fèi)的時(shí)間相同。緯度線總長L米。現(xiàn)在要你求出它們跳了幾次以后才會(huì)碰面。,工大ACM團(tuán)隊(duì),POJ 1061,輸入只包括一行5個(gè)整數(shù)x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。輸出碰面所需要的跳躍次數(shù)，如果永遠(yuǎn)不可能碰面則輸出一行

29、"Impossible",工大ACM團(tuán)隊(duì),POJ 1061,Input 輸入只包括一行5個(gè)整數(shù)x，y，m，n，L，其中x≠y < 2000000000，0 < m、n < 2000000000，0 < L < 2100000000。Output 輸出碰面所需要的跳躍次數(shù)，如果永遠(yuǎn)不可能碰面則輸出一行"Impossible"Sample Input 1

30、2 3 4 5 Sample Output 4,工大ACM團(tuán)隊(duì),解題思路,此題其實(shí)就是擴(kuò)展歐幾里德算法－求解不定方程，線性同余方程。　　設(shè)過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只要上式存在

31、整數(shù)解，則兩青蛙能相遇，否則不能。首先想到的一個(gè)方法是用兩次for循環(huán)來枚舉s,l的值，看是否存在s,l的整數(shù)解，若存在則輸入最小的s，但顯然這種方法是不可取的，誰也不知道最小的s是多大，如果最小的s很大的話，超時(shí)是明顯的。,工大ACM團(tuán)隊(duì),解題思路,求a * x + b * y = n的整數(shù)解?！?、先計(jì)算Gcd(a,b)，若n不能被Gcd(a,b)整除，則方程無整數(shù)解；否則，在方程兩邊同時(shí)除以Gcd(a,b)，得到新的不定方程a

32、' * x + b' * y = n'，此時(shí)Gcd(a',b')=1;   2、利用上面所說的歐幾里德算法求出方程a' * x + b' * y = 1的一組整數(shù)解x0,y0，則n' * x0,n' * y0是方程a' * x + b' * y = n'的一組整數(shù)解；　3、根據(jù)數(shù)論中的相關(guān)定理，可得方程a&#

33、39; * 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-b*t。x

34、的最小的可能值是0令x=0，可求出當(dāng)x最小時(shí)的t的取值，但由于x=0是可能的最小取值，實(shí)際上可能x根本取不到0，那么由計(jì)算機(jī)的取整除法可知：由 t=c*k1/b算出的t，代回x=c*k1-b*t中。求出的x可能會(huì)小于0，此時(shí)令t=t+1，求出的x必大于0；如果代回后x仍是大于等于0的，那么不需要再做修正。,工大ACM團(tuán)隊(duì),核心代碼分析,while(scanf("%I64d%I64d%I64d%I64d%I64d"

35、,&x,&y,&m,&n,&l)!=EOF) { a=n-m; b=l; c=x-y; r=gcd(a,b); if(c%r) { printf("Impossible\n"); continue; } a/=r; b/=r; c/=r;

36、 exgcd(a,b,k1,k2); t=c*k1/b; k1=c*k1-t*b; if(k1<0) k1+=b; printf("%I64d\n",k1); },工大ACM團(tuán)隊(duì),練習(xí)題,pku:1006, 1014, 1023, 1061, 1152, 1183, 1730, 2262, 2356