2013acm簡單數(shù)論

1、1,ACM 數(shù)論,http://10.7.18.82/vjudge/contest/contest/view.action?cid=6#overview,2,初等數(shù)論的概念,整除性和約數(shù)：假設(shè)d和a是整數(shù)，d|a（讀作d整除a），意味著存在某個整數(shù)k，有a=kd。如果d|a，并且d≥0，則稱d是a的約數(shù)。每個整數(shù)a都可以被其平凡約數(shù)1和a整除，a的非平凡約數(shù)也稱為a的因子。,3,初等數(shù)論的概念,素數(shù)和合數(shù)對于某個整數(shù)a>1

2、，如果它僅有平凡約數(shù)1和a則稱p是素數(shù)。否則p是合數(shù)。可以證明素數(shù)有無限多個。篩法求素數(shù)。,4,求素數(shù)方法,1）p[N]存儲所有的素數(shù)，二重循環(huán)，用已經(jīng)求出的不大于平方根的所有素數(shù)試除for(i=2;i<n;++i)for(j=0;j<m && p[j]*p[j]<=i;++j)如果p[j]整除i，則i不是素數(shù)如果都不能整除，則i是素數(shù)，添加到素數(shù)列表p[N];(m++),5,2）給定一個范

3、圍（求這個范圍內(nèi)的素數(shù)），進行如下步驟： 0.從2開始，2是第一個素數(shù)。也是第一個新素數(shù)。取出2。 1.篩掉所有新素數(shù)的倍數(shù)。 2.留下來的數(shù)里面第一個（最小的）是新素數(shù)。取出這個新素數(shù)。 3.重復(fù)1和2直到?jīng)]有數(shù)存在。,Eratosthenes篩法,6,O(n)篩素數(shù),void Init(){ int i,j,q,n,cnt=0; memset(mark,0,sizeof(mark)); n=1000;

4、 for(i=2;in)break; mark[prime[j]*i]=prime[j];if(mark[i]==prime[j]){//printf("%d %d mark=%d\n",i,j,mark[i]);break;}} }} 內(nèi)網(wǎng)B、C題,7,初等數(shù)論概念,除法定理，余數(shù)除法定理：對任意整數(shù)a和任意正整數(shù)n，存在唯一的整數(shù)q和

5、r，使得a=qn+r，其中0≤r<n。值q成為除法的商，值r=a(mod n)稱為除法的余數(shù)。,8,初等數(shù)論的概念,公約數(shù)與最大公約數(shù)d是a的約數(shù)并且也是b的約數(shù)，則d是a和b的公約數(shù)。兩個不同時為0的整數(shù)a和b的最大公約數(shù)表示為gcd(a, b)。,9,初等數(shù)論的概念,gcd(a, b) 的性質(zhì)：定理：如果a，b是不全為0的任意整數(shù)，則gcd(a, b)是a與b的線性組合{ax+by:x,y∈Z}中的最小正元素。推論1

6、：對于任意整數(shù)a，b，如果d|a并且d|b，則d|gcd(a, b)。推論2：對于所有整數(shù)a和b以及任意非負整數(shù)n，gcd(an, bn)=n*gcd(a,b)。推論3：對所有正整數(shù)n，a和b，如果n|ab并且gcd(a, n)=1，則n|b。,10,初等數(shù)論的概念,互質(zhì)數(shù)：如果兩個整數(shù)a與b只有公因數(shù)1，即如果gcd(a, b)=1，則a與b稱為互質(zhì)數(shù)（互素）。定理：對任意整數(shù)a，b和p，如果gcd(a, p)=1且gcd(b

7、, p)=1，則gcd(ab, p) = 1。,11,最大公約數(shù) gcd（最大公因子）,Euclidean算法求兩個正整數(shù)a和b的gcd。先令r0為a，r1為b，接著執(zhí)行如下運算：,12,最大公約數(shù),GCD遞歸定理：對任意非負整數(shù)a和任意正整數(shù)b，gcd(a, b) = gcd(b, a mod b)。,13,歐幾里德算法：EUCLID(a, b) if b = 0 than return a else

8、 return EUCLID(b, a % b),,14,二進制最大公約數(shù)算法：如果a和b都是都是偶數(shù)，那么gcd(a, b) = 2gcd(a/2, b/2)。如果a是奇數(shù)，b是偶數(shù)，那么gcd(a, b) = gcd(a, b/2)。如果a和b都是奇數(shù)，那么gcd(a, b) = ((a–b)/2, b)。吉林大學(xué)模板,,15,,思考： 將兩個整數(shù)的歐幾里德算法推廣到求m個整數(shù)的最大公約數(shù)。（兩種方法）,1

9、6,Extended-Euclidean 算法,定理：對于不完全為0的非負整數(shù)a，b，gcd（a，b）表示a，b的最大公約數(shù)d，必然存在整數(shù)對x，y，使得gcd（a，b）=d=ax+by。,17,擴展歐幾里德算法,對于gcd(a,b) = d，對(a, b)用歐幾里德輾轉(zhuǎn)相除會最終得到(d, 0)。此時對于把a =d, b = 0 代入a*x + b*y = d，顯然x = 1，y可以為任意值。我們可以用a = d, b = 0的情況

10、逆推出來任何gcd(a, b) = d 滿足a*x + b*y = d的解。如果x0，y0是b*x + (a%b)*y = d 的解，那么對于a*x + b*y = d的解呢？,18,擴展歐幾里德算法,b*x + (a%b)*y = d → b*x + (a - [a/b]*b)*y = a*y + b*(x - [a/b]*y)，所以a*x + b*y = d的解x1 = y0， y1= x0 - [a/b]*

11、y0; 這樣我們可以程序迭代了。,注：a,b為正整數(shù)，設(shè)集合A = {x*a+y*b|x,y是整數(shù)}，則A中最小正元素是gcd(a,b),19,擴展歐幾里德算法：EXTENDED-EUCLID(a, b) if b = 0 then return (a, 1, 0) (d’,x’,y’) ← EXTENDED-EUCLID(b, a%b) (d, x, y) ← (d’, y’, x’ –

12、(a/b) * y’) return (d, x, y),20,擴展歐幾里德算法,21,例如：a＝4864，b＝3458，則由上述算法可得gcd（4864，3458）＝38，且（4864）（38）＋（3458）（－45）＝38,22,LCM(Least Common Multiple),有了 GCD, LCM 就好辦了LCM ( a, b ) = a * b / GCD ( a, b ) 實際上最好寫成a/GCD(a,b)

13、*b思考：為什么下面的寫法好？,23,初等數(shù)論概念,唯一因子分解唯一質(zhì)因子分解定理：合數(shù)a僅能以一種方式，寫成如下的乘積形式：a=p1e1p2e2…prer其中pi為素數(shù)，p1<p2<…<pr，且ei為正整數(shù)。,24,其他一些關(guān)于約數(shù)的公式,,25,n！的素因子分解式,26,反素數(shù),問題描述:對于任何正整數(shù)x,其約數(shù)的個數(shù)記做g(x).例如g(1)=1,g(6)=4.如果某個正整數(shù)x滿足:對于任意i(0&

14、lt;i<x),都有g(shù)(i)<g(x),則稱x為反素數(shù).現(xiàn)在給一個N,求出不超過N的最大的反素數(shù).比如:輸入1000 輸出 840,27,思維過程:求[1..N]中最大的反素數(shù)-->求約數(shù)最多的數(shù)如果求約數(shù)的個數(shù) 756=2^2*3^3*7^1(2+1)*(3+1)*(1+1)=24基于上述結(jié)論,給出算法:按照質(zhì)因數(shù)大小遞增順序搜索每一個質(zhì)因子,枚舉每一個質(zhì)因子為了剪枝:性質(zhì)一:一個反素數(shù)的質(zhì)因子必

15、然是從2開始連續(xù)的質(zhì)數(shù).因為最多只需要10個素數(shù)構(gòu)造:2,3,5,7,11,13,17,19,23,29性質(zhì)二:p=2^t1*3^t2*5^t3*7^t4.....必然t1>=t2>=t3>=....內(nèi)網(wǎng)F題,28,同余,設(shè)m≠0，若m∣a－b，即a－b＝km，則稱a同余于b模m，記為a、b關(guān)于模m同余的充要條件是整數(shù)a和b被同一正整數(shù)m除時，有相同的余數(shù)。,29,同余的性質(zhì),30,同余的性質(zhì),若m≥1，（

16、a，m）＝1，則存在c使得 ca≡1（mod m）我們把c稱為是a對模m的逆，記為 a－1（mod m）或a－1可以用擴展歐幾里德算法求a－1應(yīng)用：(a/b)%m->(a%m)/(b%m)？省賽,31,例：求3406寫成十進位數(shù)時的個位數(shù).,根據(jù)題意是要求a滿足3406 ≡a（mod 10）顯然32 ≡9 ≡－1 （mod 10），34 ≡1 （mod 10），從而

17、3404 ≡1 （mod 10），因此3406 ≡ 3404 × 32 ≡9（mod 10）所以個位數(shù)是9.,32,根據(jù)整數(shù)模n所得的余數(shù)，可以把整數(shù)分成n個等價類：[0],[1],…,[n-1]。包含整數(shù)的模n等價類為：[a]n={a+kn| k∈Z},33,求解模線性方程,定理：方程ax=b(mod n)對于未知量x有解，當(dāng)且僅當(dāng)gcd(a, n)|b定理：方程ax=b(mod n)或者對模n有d個不同的解，其

18、中d=gcd(a, n)或者無解。,34,求解模線性方程,定理：設(shè)d=gcd(a, n)，假定對整數(shù)x’和y’，有d=ax’+ny’。如果d|b，則方程ax=b(modn)有一個解的值為x0，滿足x0=x’(b/d)mod n。,35,求解模線性方程,定理：假設(shè)方程ax=b(mod n)有解（即有d|b，其中d=gcd(a, n)），x0是該方程的任意一個解，則該方程對模n恰有d個不同的解，分別為：xi=x0+i(n/d)(i = 1,

19、 2, …, d-1)。,36,求解模線性方程,MODULAR-LINEAR_EQUATION_SOLVER(a, b, n) (d,x’,y’) ← EXTENDED-EUCLID(a, n) if (d | b) then x0 ← x’(b/d)mod n for i ← 0 to d-1 do print(x0 + i(n / d)) mod n e

20、lse print “no solution”,37,模線性方程,定理：對任意n>1，如果gcd(a, n)=1，則方程ax=b(mod n)對模n有唯一解。定理：對任意n>1，如果gcd(a, n)=1，則方程ax=1(mod n)對模n有唯一解，否則無解。,38,公元5－6世紀前后的《孫子算經(jīng)》中有“物不知數(shù)”問題：“今有物不知其數(shù)，三三數(shù)之余二 ，五五數(shù)之余三 ，七七數(shù)之余二，問物幾何？”答為“23”。也就是求同余式

21、組x≡2 （mod3），x≡3 （mod5 ），x≡2 （mod7）的正整數(shù)解。明朝程大位用歌謠給出了該題的解法：“三人同行七十稀，五樹梅花廿一枝，七子團圓月正半，除百零五便得知?！奔唇鉃?x≡2×70＋3×21＋2×15≡233≡23(mod105）。,中國剩余定理,39,中國剩余定理（孫子定理）,40,,問題：給定兩兩互質(zhì)的正整數(shù)n1,n2,...,nk，要求找到最小的正整數(shù)a，滿足a≡ai (mo

22、d ni)算法步驟:令n=n1n2...nk，mi=n/ni顯然gcd(mi,ni)=1，解模線性方程，計算出xi滿足mixi≡1 (mod ni)a≡a1x1m1+a2x2m2+...+akxkmk (mod n),41,歐拉函數(shù),Euler函數(shù) ：設(shè)m是正整數(shù)，1，2，…，m中與m互素的數(shù)的個數(shù)。定理：,42,歐拉定理的推廣形式當(dāng)x≥? (m)時，A­x≡A(x mod ?(m)+ ?(m))

23、(mod m),43,定理：如果p是一個奇素數(shù)且e≥1，則方程x2=1(mod pe)僅有兩個解：x=1和x=-1。定理：如果對模n存在1的非平凡平方根，則n是和數(shù)。,44,元素的冪,3k mod 7為：i 0 1 2 3 4 5 6 7 8 9 10 113k mod 7 1 3 2 6 4 5 1 3 2 6 4 52k mod 7為：i 0 1 2 3 4 5

24、6 7 8 9 10 112k mod 7 1 2 4 1 2 4 1 2 4 1 2 4,45,素數(shù)測試,46,素數(shù)測試,47,素數(shù)測試,48,素數(shù)測試,要判斷一個整數(shù)n是不是素數(shù)，應(yīng)用費馬定理：如果n是素數(shù)，那么對于任意的a都滿足an-1=1(mod n)。所以可以通過隨機選取若干個a，來檢驗n是否是素數(shù)。,49,素數(shù)測試,如果n是合數(shù)，并且滿足an-1=1(mod n)那么就說n是一個基為a的偽素數(shù)。,50,素數(shù)測試,然而

25、，并不能通過增加隨機次數(shù)來增加這種測試的正確性，因為存在一些合數(shù)，也滿足對于任意的a，an-1=1(mod n)通常把這樣的合數(shù)稱為Carmichael數(shù)。前三個Carmichael數(shù)是561，1105和1729。Carmichael數(shù)是非常少的，在小于100000000的數(shù)中，只有255個Carmichael數(shù)。,51,大數(shù)的素性檢測,Rabin-Miller素數(shù)測試非素數(shù)通過測試概率為 ¼Pollard-ρ算法大數(shù)