北京大學(xué)acm暑期課講義-lcc-數(shù)論

1、ACM中的數(shù)論,北京大學(xué)ACM隊(duì)李曄晨lccycc@qq.comhi.baidu.com/lccycc_acm,基本概念,模，同余最大公約數(shù)和最小公倍數(shù)素?cái)?shù)，互素正整數(shù)的素因數(shù)分解,本講要點(diǎn),擴(kuò)展gcd與裴蜀定理模線性方程模線性方程組—中國(guó)剩余定理高斯消元法篩法線性求素?cái)?shù)歐拉函數(shù),擴(kuò)展gcd與裴蜀定理,最大公約數(shù)：d = gcd(a,b)裴蜀定理：存在u,v使得a*u + b*v = d裴蜀定理特例

2、：若a,b互質(zhì)，gcd(a,b) = 1則存在u,v 使得 a*u + b*v = 1設(shè) a = pd, b = qd, 則p,q互質(zhì)（為什么？）裴蜀定理 pdu + qdv = d -> pu + qv = 1 轉(zhuǎn)化為特例,裴蜀定理的 證明,直接構(gòu)造出u,vau + bv = d(a-b)u + b(u+v) = d令a’ = a%

3、b, 令t使得a = b*t + a’t = [a/b](a-tb)u + b(tu + v) = da’u + b(tu+v) = d令v’ = tu+v, 得到a’u + bv’ = d,令v’ = tu+v, 得到a’u + bv’ = dv = v’ – tu 若知道(u, v’)則可知道(u,v)int gcd(int a, int b){return b==0?a:gcd(b,a%b);}int

4、ex_gcd(int a,int b, int &u, int &v){If (b == 0){u = 1, v = 0;Return a;}int d = ex_gcd(b, a%b, v, u);v = v - a/b *u;return d;},擴(kuò)展gcd算法,模線性方程,ax = d (mod b) abd 已知求x轉(zhuǎn)化為ax + by = d 用擴(kuò)展gcd求x,y注意2

5、容易溢出在求x,y的中間步對(duì)其mod b處理,中國(guó)剩余定理,設(shè)n組數(shù)(ai, bi), 其中bi兩兩互素求x使得 x = a1 mod b1x = a2 mod b2...x = an mod bn,中國(guó)剩余定理,令B = b1*b2*b3…*bn令ci = B/bi = b1*b2*..*b(i-1)*b(i+1)..*bn顯然有ci 與bi互素，從而存在mi滿足mi*ci = bi (mod b)x = a

6、1b1m1 + a2b2m2 + …+anbnmn為什么這個(gè)x是解？聯(lián)想：拉格朗日插值公式！,中國(guó)剩余定理,設(shè)n組數(shù)(ai, bi), 其中bi兩兩互素如果bi不是兩兩互素呢？另一個(gè)角度看此問(wèn)題 x = a1( mod b1) x = a2( mod b2)->x + u*b1 = a1, x - v*b2 = a2-> u*b1 + v*b2 = (a1-a2)化為裴蜀定理的一般情況，有解當(dāng)且僅當(dāng) gcd

7、(b1, b2) | (a1-a2),中國(guó)剩余定理的一般情況,于是我們得到了一個(gè)初始的(u,v)記做(u0,v0)u*b1 + v*b2 = (a1-a2) 的所有解(u,v) 滿足u = u0 + tb2/gcd(b1,b2)v = v0 – tb1/gcd(b1,b2)（為什么？） x + u*b1 = a1x 的解空間為 a1 – u0b1 - t(b1b2)/gcd(b1b2) = a1 - u0b1 - t*L

8、CM(b1,b2),中國(guó)剩余定理的一般情況,x = a1 - u0b1 - t*LCM(b1,b2)等價(jià)于：我們把前兩個(gè)方程變成了一個(gè)方程：x = a1-u0b1 (mod LCM(b1,b2) )每次方程數(shù)-1 繼續(xù)這樣消下去 就可以得出x的可行解空間。注意：擴(kuò)展歐幾里得算法給出的是一個(gè)解空間！,高斯消元法,a11x1 + a12x2 + .. + a1nxn = b1a21x1 + a22x2 + .. + a2nxn

9、= b2…am1 x1 + am2x2 + .. + amnxn = bm求解 一般m=n如果是在mod p的線性空間下呢？(p素?cái)?shù)),hdu 3949 XOR,求n個(gè)int數(shù)里面x或的第k大值N有多大，基向量都不超過(guò)32個(gè)mod2高斯消元求出基向量就可以代表這n個(gè)int的所有xor結(jié)果將k分解二進(jìn)制,篩素?cái)?shù),篩素?cái)?shù)大家都會(huì)初始2..n每次取出第一個(gè)沒(méi)被刪掉的元素p 必然是素?cái)?shù)將p的倍數(shù)都刪掉復(fù)雜度：n/1 +

10、 n/2 + n/3 + n/5 + .. + n/p,線性篩素?cái)?shù),一個(gè)元素會(huì)被刪好多次。如何優(yōu)化成線性？,對(duì)每個(gè)素?cái)?shù)p 考慮所有i, i的最小素因子>=p將i*p去掉如何代碼實(shí)現(xiàn)？,,memset(Prime,0,sizeof(Prime));memset(IsPrime,1,sizeof(IsPrime));for (int i=2;i<=n;i++){ if (Is

11、Prime[i]) Prime[num++] = i; for (int j=1;j<num && i*Prime[j]<=n;j++){ IsPrime[i*Prime[j]] = 0; if (i%Prime[j] == 0) break; }},歐拉函數(shù),? (n) = 1..n中與n互質(zhì)的數(shù)的

12、個(gè)數(shù)如何求? (n)?素因子展開(kāi)+容斥原理令n = p1r1p2r2...pkrk?(n)=n*(1-1/p1)*(1-1/p2)*...*(1-1/pk)（為什么？）,歐拉定理,若a和n互質(zhì)，則a?(n)≡1 (mod n)歐拉定理的推廣形式當(dāng)x≥? (m)時(shí)，ax≡a(x mod ?(n)+ ?(n)) (mod n)不需要互素用途：計(jì)算a^b^c^d^e..的高階冪次取模（如何計(jì)算？）,POJ3696 The

13、Luckiest number,題目大意:定義只含有數(shù)字8的數(shù)為幸運(yùn)數(shù)給定正整數(shù)L，求L的所有倍數(shù)中最小的幸運(yùn)數(shù)算法思路：設(shè)最終答案為x個(gè)8，則x滿足(10x-1)*8/9≡0 (mod L)化簡(jiǎn)：10x≡1 (mod n)，其中n=9L/gcd(9L,8)這是一個(gè)離散對(duì)數(shù)的問(wèn)題，求解方法如下：若gcd(10,n)>1，無(wú)解若gcd(10,n)=1，由歐拉定理：10?(n)≡1 (mod n)。可以證明，x為?(n

14、)的約數(shù)，從小到大枚舉約數(shù)即可10l≡1 (mod n) 則成立的最小 l 是? (n)的約數(shù) 這個(gè)性質(zhì)競(jìng)賽中經(jīng)常用到,POJ2478 Farey Sequence,求所有分母不大于n的既約真分?jǐn)?shù)個(gè)數(shù),分母為x的既約真分?jǐn)?shù)有?(x)個(gè)?分母不大于n的既約真分?jǐn)?shù)個(gè)數(shù)為?(1)+ ?(2)+...+ ?(n)如何快速求出?(1), … ?(n)?對(duì)?(x)，分解然后遞推,莫比烏斯函數(shù),設(shè)n=p1r1p2r2...pkrk