acm-數(shù)論a

1、tom@nenu_OTZ,數(shù)論,,求素?cái)?shù)方法,怎么判斷一個(gè)數(shù)是否為素?cái)?shù)？ bool IsPrime(unsigned n){ for (unsigned i=2;i<n;++i) { //和比它小的所有的數(shù)相除,如果都除不盡，證明素?cái)?shù) if (n%i==0)//除盡了，則是合數(shù) return false; } return true;}笨蛋的作法：一

2、個(gè)數(shù)去除以比它的一半還要大的數(shù)，一定除不盡，所以還用判斷嗎？？,下面是中學(xué)生的做法：,bool IsPrime(unsigned n){ for(unsigned i=2;i<n/2+1;++i) { // 和比它的一半小數(shù)相除，如果都除不盡，證明素?cái)?shù) if ( 0 == n % i ) { // 除盡了，合數(shù) return false; }

3、 } return true; // 都沒除盡，素?cái)?shù)}//復(fù)雜度是o(n*sqrt(n))，,中學(xué)生的做法,但是當(dāng)n很大的時(shí)候，比如n=10000000時(shí)，n*sqrt(n)>30000000000,數(shù)量級相當(dāng)大。在一般的機(jī)子它不是一秒鐘跑不出結(jié)果，它是好幾分鐘都跑不出結(jié)果 -_-！，想鍛煉耐心的同學(xué)不妨試一試在程序設(shè)計(jì)競賽中就必須要設(shè)計(jì)出一種更好的算法要求能在幾秒鐘甚至一秒鐘之內(nèi)找出n以內(nèi)的所有素?cái)?shù)。

4、于是就有了素?cái)?shù)篩法。,篩法求素?cái)?shù),void Prime(int max){ memset(flag, true, sizeof(flag)); for(int i = 2; i <= max / 2; i++) { if(flag[i]) for(int j = i << 1 ; j <= max; j += i)

5、flag[j] = false; } for(int i = 2 ; i <= max; i++) if(flag[i]) prime[size++] = i;},篩法求素?cái)?shù),可以再進(jìn)一步化為二次篩選法，就是欲求n以內(nèi)的素?cái)?shù)，就先把sqrt(n)內(nèi)的素?cái)?shù)求出來，用已經(jīng)求得的素?cái)?shù)來篩出后面的合數(shù)一個(gè)合數(shù)必然可以由兩個(gè)或多個(gè)質(zhì)數(shù)相乘而得到。那么如果一個(gè)數(shù)不能被比它的一半小的所

6、有的質(zhì)數(shù)整除，那么比它一半小的所有的合數(shù)也一樣不可能整除它。高斯猜測，n以內(nèi)的素?cái)?shù)個(gè)數(shù)大約與n/ln(n)相當(dāng)，或者說，當(dāng)n很大時(shí)，兩者數(shù)量級相同。這就是著名的素?cái)?shù)定理。,大數(shù)的素性檢測,Rabin-Miller素?cái)?shù)測試非素?cái)?shù)通過測試概率為 ¼Pollard-ρ算法大數(shù)的快速分解,這兩種算法在此不予以介紹，有興趣的同學(xué)可以到google上搜索或參看相關(guān)書籍,二分法in乘方,如何計(jì)算a^n ？1）計(jì)算a*a*a*…*

7、a*a*a，需要計(jì)算n-1次乘法，時(shí)間復(fù)雜度O(n)2）考慮實(shí)例a^4，計(jì)算b=a*a，再算c=b*b，則c=a^4，但是只用了兩次乘法，效率提高。比如a^9=a*(a^4)*(a^4)，只需用4次乘法，一般的，a^n時(shí)間復(fù)雜度為O(logn),二分法in乘方,為了講清這個(gè)算法，舉一個(gè)例子2^7：2*2*2*2*2*2*2 兩兩分開：(2*2)*(2*2)*(2*2)*2 如果用2*2來計(jì)算，那么指數(shù)就可以除以2了，不過剩了一個(gè)，

8、稍后再單獨(dú)乘上它。再次兩兩分開，指數(shù)除以2： ((2*2)*(2*2))*(2*2)*2 實(shí)際上最后一個(gè)括號里的2 * 2是這回又剩下的，那么，稍后再單獨(dú)乘上它 現(xiàn)在指數(shù)已經(jīng)為1了，可以計(jì)算最終結(jié)果了：16*4*2=128,二分法in乘方,第二種算法與二進(jìn)制的關(guān)系9=(1001)2，a^9=a^8*a;10=(1010)2，a^10=a^8*a^2;從二進(jìn)制最后一位開始，如果第k位是1，就乘以a^(2^(k-1)),計(jì)算

9、每個(gè)a^(2^k)需要logn，得到答案最多需要乘logn次，所以復(fù)雜度是O(logn)如果把a(bǔ)看作矩陣，上面方法可應(yīng)用于矩陣乘方（注：這并不是最快的辦法，有興趣的同學(xué)可以做一下poj3134）,unsigned Power(unsigned n, unsigned p) { // 計(jì)算n的p次方 unsigned odd = 1; //oddk用來計(jì)算“剩下的”乘積 while (p > 1) {

10、// 一直計(jì)算到指數(shù)小于或等于1 if (( p & 1 )!=0) { // 判斷p是否奇數(shù)，偶數(shù)的最低位必為0 odd *= n; // 若odd為奇數(shù)，則把“剩下的”乘起來 } n *= n; // 主體乘方 p /= 2; // 指數(shù)除以2 } return n * odd; // 最后把主體和“剩下的”乘起來作

11、為結(jié)果},改進(jìn)乘方算法應(yīng)用于fibonacci,,普通的算法求Fn的時(shí)間復(fù)雜度為O(n)，當(dāng)然如果要求求出所有的Fn，這種已經(jīng)是最優(yōu)的了，但是如果只求某一個(gè)Fn，可以改進(jìn),,蒙格馬利快速冪模算法,后面我們會(huì)用到這樣一種運(yùn)算：(X^Y)%Z問題是當(dāng)X和Y很大時(shí)，只有32位的整型變量如何能夠有效的計(jì)算出結(jié)果？考慮上面那份最終的優(yōu)化代碼和再上面提到過的積模分解公式，我想你也許會(huì)猛拍一下腦門，吸口氣說：“哦，我懂了！”。,蒙格馬利快速冪模

12、算法,下面的講解是給尚沒有做出這樣動(dòng)作的同學(xué)們準(zhǔn)備的。X^Y可以看作Y個(gè)X相乘，即然有積模分解公式，那么我們就可以把Y個(gè)X相乘再取模的過程分解開來，比如：(17^25)%29則可分解為：( ( 17 * 17 ) % 29 * ( 17 * 17 ) % 29 * ……如果用上面的代碼將這個(gè)過程優(yōu)化，那么我們就得到了著名的“蒙格馬利”快速冪模算法：,unsigned Montgomery(unsigned n, unsigned

13、p, unsigned m){ // 快速計(jì)算 (n ^ e) % m 的值，與power算法極類似 unsigned r = n % m; // 這里的r可不能省 unsigned k = 1; while (p > 1) { if ((p & 1)!=0) { k = (k * r) % m; // 直接取模 }

14、 r = (r * r) % m; // 同上 p /= 2; } return (r * k) % m; // 還是同上},上面的代碼還可以優(yōu)化。下面是蒙格馬利極速版：unsigned Montgomery(unsigned n,unsigned p,unsigned m){ //快速計(jì)算(n^e)%m的值 unsignedk=1; n%=m; w

15、hile(p!=1) { if(0!=(p&1))k=(k*n)%m; n=(n*n)%m; p>>=1; } return(n*k)%m;},GCD（Great Common Divisor),定理：gcd(a,b) = gcd(b,a mod b) Euclid 算法int gcd ( int a, int b ) {int mo

16、d;while ( mod = a % b ) a = b, b = mod;return b;}//注意這里面必須a,b都為正數(shù)，否則要加其他判斷語句,LCM(Least Common Multiple),有了 GCD, LCM 就好辦了↓LCM ( a, b ) = a * b / GCD ( a, b ) 實(shí)際上最好寫成a/GCD(a,b)*b思考：為什么下面的寫法好？,擴(kuò)展歐幾里得算法,同時(shí)求出 v, u 使g

17、cd ( a, b ) = u * a + v * b（重要）非遞歸的不好寫，建議寫遞歸的,擴(kuò)展歐幾里得算法,注意到對于gcd(a,b) = d 我們對(a, b)用歐幾里德輾轉(zhuǎn)相除會(huì)最終得到(d, 0)此時(shí)對于把a(bǔ) =d, b = 0 帶入a*x + b*y = d，顯然x = 1，y可以為任意值，這里y可以為任意值就意味著解會(huì)有無數(shù)個(gè)。我們可以用a = d, b = 0的情況逆推出來任何gcd(a, b) = d 滿足a*x

18、 + b*y = d的解。如果x0, y0是b*x + (a%b)*y = d 的解，那么對于a*x + b*y = d的解呢？,擴(kuò)展歐幾里得算法,b*x0 + (a%b)*y0 =d =>b*x 0+ (a - [a/b]*b)*y0 =d => a*y 0+ b*(x0 - [a/b]*y0)=d，所以a*x + b*y = d的解x1 = y0， y1 = x0 - [a/b]*y0;

19、 這樣我們可以程序迭代了。,注：a,b為正整數(shù)，設(shè)集合A = {x*a+y*b|x,y是整數(shù)}，則A中最小正元素是gcd(a,b),擴(kuò)展歐幾里得算法,int exGcd(int a, int b, int &x, int &y){ if(b == 0) { x = 1; y = 0; return a; } int r = exGcd(b

20、, a % b, x, y); int t = x; x = y; y = t - a / b * y; return r;},其他一些關(guān)于約數(shù)的公式,若n=p1e1p2e2…prer，則 n的因數(shù)個(gè)數(shù)為 (1+e1)*(1+e2)*……(1+er) n所有因數(shù)的和為(1+p1+p12+…+p1e1)*(1+p2+p22+…+p2e2) *…*(1+pr+pr2+…+prer),

21、,歐拉函數(shù),(x)表示與x互質(zhì)且小于x的正整數(shù)的個(gè)數(shù)如果x為素?cái)?shù)，則歐拉函數(shù)等于x-1例如φ(8)=4，因?yàn)?,3,5,7均和8互質(zhì)。 若n是質(zhì)數(shù)p的k次冪，φ(n)=p^k-p^(k-1)=(p-1)p^(k-1)，因?yàn)槌藀的倍數(shù)外，其他數(shù)都跟n互質(zhì)。歐拉函數(shù)是積性函數(shù)——若m,n互質(zhì)，φ(mn)=φ(m)φ(n)。,,歐拉函數(shù),求法：將x分解為p1^n1*p2^n2*…pk^nk，則歐拉函數(shù)=p1^(n1-1)*…

22、*pk^(nk-1) *(p1-1)*…*(pk-1),歐拉函數(shù),歐拉函數(shù)的編程實(shí)現(xiàn) 利用歐拉函數(shù)和它本身不同質(zhì)因數(shù)的關(guān)系，用篩法計(jì)算出某個(gè)范圍內(nèi)所有數(shù)的歐拉函數(shù)值。 歐拉函數(shù)和它本身不同質(zhì)因數(shù)的關(guān)系： ψ（１０）＝１０×（１－１/２）×（１－１/５）＝４； ψ（３０）＝３０×（１－１/２）×（１－１/３）×（１－１/５）＝８

23、； ψ（４９）＝４９×（１－１/７）＝４２,歐拉函數(shù),int euler(int n) { int i, j, k; int res = n; for(i = 0; p[i] 1) res = res / n * (n-1); return res;},.x的二進(jìn)制長度,語法：result=BitLength(int x); 參數(shù)：x：測長的x返回值：x的二進(jìn)制長度源程序：int

24、BitLength(int x){ int d = 0; while (x > 0) { x >>= 1; d++; } return d;},返回x的二進(jìn)制表示中從低到高的第i位,2.語法：result=BitAt(int x, int i); 參數(shù)： x：十進(jìn)制 xi：要求二進(jìn)制的第i位返回值：返回x的二進(jìn)制表示中從低到高的第i位注意：最

25、低位為第一位源程序：int BitAt(int x, int i){ return ( x & (1 << (i-1)) );},Exercise,歐拉函數(shù)：pku2478 pku2480 pku2407 pku1284快速冪模pku3070 http://acm.nit.net.cn/showproblem.jsp?pid=1019pku 3233(選作)pku1845篩選法PKU