2013acm簡(jiǎn)單數(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），意味著存在某個(gè)整數(shù)k，有a=kd。如果d|a，并且d≥0，則稱d是a的約數(shù)。每個(gè)整數(shù)a都可以被其平凡約數(shù)1和a整除，a的非平凡約數(shù)也稱為a的因子。,3,初等數(shù)論的概念,素?cái)?shù)和合數(shù)對(duì)于某個(gè)整數(shù)a>1

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

3、圍（求這個(gè)范圍內(nèi)的素?cái)?shù)），進(jìn)行如下步驟： 0.從2開(kāi)始，2是第一個(gè)素?cái)?shù)。也是第一個(gè)新素?cái)?shù)。取出2。 1.篩掉所有新素?cái)?shù)的倍數(shù)。 2.留下來(lái)的數(shù)里面第一個(gè)（最小的）是新素?cái)?shù)。取出這個(gè)新素?cái)?shù)。 3.重復(fù)1和2直到?jīng)]有數(shù)存在。,Eratosthenes篩法,6,O(n)篩素?cái)?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ù)除法定理：對(duì)任意整數(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ù)。兩個(gè)不同時(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、：對(duì)于任意整數(shù)a，b，如果d|a并且d|b，則d|gcd(a, b)。推論2：對(duì)于所有整數(shù)a和b以及任意非負(fù)整數(shù)n，gcd(an, bn)=n*gcd(a,b)。推論3：對(duì)所有正整數(shù)n，a和b，如果n|ab并且gcd(a, n)=1，則n|b。,10,初等數(shù)論的概念,互質(zhì)數(shù)：如果兩個(gè)整數(shù)a與b只有公因數(shù)1，即如果gcd(a, b)=1，則a與b稱為互質(zhì)數(shù)（互素）。定理：對(duì)任意整數(shù)a，b和p，如果gcd(a, p)=1且gcd(b

7、, p)=1，則gcd(ab, p) = 1。,11,最大公約數(shù) gcd（最大公因子）,Euclidean算法求兩個(gè)正整數(shù)a和b的gcd。先令r0為a，r1為b，接著執(zhí)行如下運(yùn)算：,12,最大公約數(shù),GCD遞歸定理：對(duì)任意非負(fù)整數(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,二進(jìn)制最大公約數(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,,思考： 將兩個(gè)整數(shù)的歐幾里德算法推廣到求m個(gè)整數(shù)的最大公約數(shù)。（兩種方法）,1

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

10、逆推出來(lái)任何gcd(a, b) = d 滿足a*x + b*y = d的解。如果x0，y0是b*x + (a%b)*y = d 的解，那么對(duì)于a*x + b*y = d的解呢？,18,擴(kuò)展歐幾里德算法,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,擴(kuò)展歐幾里德算法：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,擴(kuò)展歐幾里德算法,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 ) 實(shí)際上最好寫成a/GCD(a,b)

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

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

15、然是從2開(kāi)始連續(xù)的質(zhì)數(shù).因?yàn)樽疃嘀恍枰?0個(gè)素?cái)?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í)，有相同的余數(shù)。,29,同余的性質(zhì),30,同余的性質(zhì),若m≥1，（

16、a，m）＝1，則存在c使得 ca≡1（mod m）我們把c稱為是a對(duì)模m的逆，記為 a－1（mod m）或a－1可以用擴(kuò)展歐幾里德算法求a－1應(yīng)用：(a/b)%m->(a%m)/(b%m)？省賽,31,例：求3406寫成十進(jìn)位數(shù)時(shí)的個(gè)位數(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）所以個(gè)位數(shù)是9.,32,根據(jù)整數(shù)模n所得的余數(shù)，可以把整數(shù)分成n個(gè)等價(jià)類：[0],[1],…,[n-1]。包含整數(shù)的模n等價(jià)類為：[a]n={a+kn| k∈Z},33,求解模線性方程,定理：方程ax=b(mod n)對(duì)于未知量x有解，當(dāng)且僅當(dāng)gcd(a, n)|b定理：方程ax=b(mod n)或者對(duì)模n有d個(gè)不同的解，其

18、中d=gcd(a, n)或者無(wú)解。,34,求解模線性方程,定理：設(shè)d=gcd(a, n)，假定對(duì)整數(shù)x’和y’，有d=ax’+ny’。如果d|b，則方程ax=b(modn)有一個(gè)解的值為x0，滿足x0=x’(b/d)mod n。,35,求解模線性方程,定理：假設(shè)方程ax=b(mod n)有解（即有d|b，其中d=gcd(a, n)），x0是該方程的任意一個(gè)解，則該方程對(duì)模n恰有d個(gè)不同的解，分別為：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,模線性方程,定理：對(duì)任意n>1，如果gcd(a, n)=1，則方程ax=b(mod n)對(duì)模n有唯一解。定理：對(duì)任意n>1，如果gcd(a, n)=1，則方程ax=1(mod n)對(duì)模n有唯一解，否則無(wú)解。,38,公元5－6世紀(jì)前后的《孫子算經(jīng)》中有“物不知數(shù)”問(wèn)題：“今有物不知其數(shù)，三三數(shù)之余二 ，五五數(shù)之余三 ，七七數(shù)之余二，問(wèn)物幾何？”答為“23”。也就是求同余式

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

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

23、(mod m),43,定理：如果p是一個(gè)奇素?cái)?shù)且e≥1，則方程x2=1(mod pe)僅有兩個(gè)解：x=1和x=-1。定理：如果對(duì)模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,素?cái)?shù)測(cè)試,46,素?cái)?shù)測(cè)試,47,素?cái)?shù)測(cè)試,48,素?cái)?shù)測(cè)試,要判斷一個(gè)整數(shù)n是不是素?cái)?shù)，應(yīng)用費(fèi)馬定理：如果n是素?cái)?shù)，那么對(duì)于任意的a都滿足an-1=1(mod n)。所以可以通過(guò)隨機(jī)選取若干個(gè)a，來(lái)檢驗(yàn)n是否是素?cái)?shù)。,49,素?cái)?shù)測(cè)試,如果n是合數(shù)，并且滿足an-1=1(mod n)那么就說(shuō)n是一個(gè)基為a的偽素?cái)?shù)。,50,素?cái)?shù)測(cè)試,然而

25、，并不能通過(guò)增加隨機(jī)次數(shù)來(lái)增加這種測(cè)試的正確性，因?yàn)榇嬖谝恍┖蠑?shù)，也滿足對(duì)于任意的a，an-1=1(mod n)通常把這樣的合數(shù)稱為Carmichael數(shù)。前三個(gè)Carmichael數(shù)是561，1105和1729。Carmichael數(shù)是非常少的，在小于100000000的數(shù)中，只有255個(gè)Carmichael數(shù)。,51,大數(shù)的素性檢測(cè),Rabin-Miller素?cái)?shù)測(cè)試非素?cái)?shù)通過(guò)測(cè)試概率為 ¼Pollard-ρ算法大數(shù)