ACM入門(mén)之?dāng)?shù)論基礎(chǔ)

1、數(shù)論Butterfly0923doraemonok求素?cái)?shù)方法1）pN存儲(chǔ)所有的素?cái)?shù)，二重循環(huán)，用已經(jīng)求出的不大于平方根的所有素?cái)?shù)試除for(i=2;in;+i)for(j=0;jm & pj*pj=n;+j)如果pj整除i，則i不是素?cái)?shù)如果都不能整除，則i是素?cái)?shù)，添加到素?cái)?shù)列表pN;素?cái)?shù)2）增加布爾型數(shù)組bN記錄是否為素?cái)?shù)，初始化所有值=1，從頭開(kāi)始遍歷，如果bi=1，則i是素?cái)?shù)，將所有的i的倍數(shù)j均修改為bj=0for(i=2;in;+i)如果bi=1則添加到素?cái)?shù)列表p，然后利用循環(huán)for(j=i;jn;j+=i) bj=0將i的所有倍數(shù)刪掉思考：試比較兩種方法效率大數(shù)的素性檢測(cè)Rabin-

2、Miller素?cái)?shù)測(cè)試非素?cái)?shù)通過(guò)測(cè)試概率為 Pollard-算法大數(shù)的快速分解二分法in乘方如何計(jì)算an ？1）計(jì)算a*a*a*a*a*a，需要計(jì)算n-1次乘法，時(shí)間復(fù)雜度O(n)2）考慮實(shí)例a4，計(jì)算b=a*a，再算c=b*b，則c=a4，但是只用了兩次乘法，效率提高。比如a9=a*(a4)*(a4)，只需用4次乘法，一般的，an時(shí)間復(fù)雜度為O(logn)二分法in乘方第二種算法與二進(jìn)制的關(guān)系9=(1001)2，a9=(12*a)222)*a10=(1010)2，a10=(12)*a)2)2*a)2從二進(jìn)制第一位開(kāi)始，遇到1就先平方乘以a，遇到0就直接平方如果把a(bǔ)看作矩陣，上面方法可應(yīng)用于矩陣

3、乘方改進(jìn)乘方算法應(yīng)用于fibonacci普通的算法求Fn的時(shí)間復(fù)雜度為O(n)，當(dāng)然如果要求求出所有的Fn，這種已經(jīng)是最優(yōu)的了，但是如果只求某一個(gè)Fn，可以改進(jìn)GCD（Great Common Divisor)Euclid 算法int gcd ( int a, int b ) int mod;while ( mod = a % b ) a = b, b = mod;return b;/注意這里面必須a,b都為正數(shù)，否則要加其他判斷語(yǔ)句Extended-Euclid 算法: 同時(shí)求出 v, u 使gcd ( a, b ) = u * a + v * b（重要）非遞歸的不好寫(xiě)，建議寫(xiě)遞歸的LCM(

4、Least Common Multiple)有了 GCD, LCM 就好辦了LCM ( a, b ) = a * b / GCD ( a, b ) 實(shí)際上最好寫(xiě)成a/GCD(a,b)*b思考：為什么下面的寫(xiě)法好？中國(guó)剩余定理中國(guó)剩余定理的內(nèi)容如下：令n=n1n2.nk，其中ni是兩兩互質(zhì)的數(shù)，則對(duì) 0=an與0=aib*x + (a - a/b*b)*y = a*y + b*(x - a/b*y)，所以a*x + b*y = d的解x1 = y0， y1 = x0 - a/b*y0; 這樣我們可以程序迭代了。Exercise1053: 哥德巴赫猜想1236: ab1430: Fibonacci1249: 分解素因子1200: Euclids Game