數(shù)論(一)

1、《算法藝術(shù)與信息學(xué)競賽》標(biāo)準(zhǔn)課件,數(shù)論(一): 概念與應(yīng)用劉汝佳,目錄,一、基本概念二、進位制三、模算術(shù)與方程四、雜題,一、基本概念,概念1: 整除關(guān)系,整除與約數(shù)、倍數(shù). 注意負數(shù)可整除性的基本性質(zhì)若a|b, a|c, 則a|(b+c)若a|b, 那么對所有整數(shù)c, a|bc若a|b, b|c, 則a|c整除關(guān)系具有傳遞性. 它是偏序關(guān)系(partial order), 是一個格,概念2: 素數(shù)和合數(shù),如果大于1的

2、正整數(shù)p僅有的正因子是1和p, 則稱p為素數(shù)(prime)大于1又不是素數(shù)的正整數(shù)稱為合數(shù)(compound)如果n是合數(shù), 則n必有一個小于或等于n1/2的素因子,定理1: 算術(shù)基本定理,每個正整數(shù)都可以惟一地表示成素數(shù)的乘積，其中素數(shù)因子從小到大依次出現(xiàn)（這里的“乘積”可以有0個、1個或多個素因子）。換句話說, 任意正整數(shù)n可以寫成n=2a1*3a2*5a3*…,其中a1,a2,a3等為非負整數(shù)這個定理也叫做惟一分解定理。它

3、是一個定理而不是公理！雖然在大多人看來，它是“顯然成立”的，但它的確是需要證明的定理,概念3: 除法和同余,令a為整數(shù)，d為正整數(shù)，那么有惟一的整數(shù)q和r，其中0≤r<d，使得a=dq+r可以用這個定理來定義除法：d叫除數(shù)，a叫被除數(shù)，q叫商，r叫余數(shù)。如果兩個數(shù)a,b除以一個數(shù)c的余數(shù)相等，說a和b關(guān)于模c同余，記作a≡b(mod c),概念4: 最大公約數(shù)和最小公倍數(shù),令a和b是不全為0的兩個整數(shù)，能使d|a和d|b的最大整

4、數(shù)稱為a和b的最大公約數(shù)，用gcd(a,b)表示，或者記為(a,b)。令a和b是不全為0的兩個整數(shù)，能使a|d和b|d的最小整數(shù)稱為a和b的最小公倍數(shù)，用lcm(a,b)表示，或者記為[a,b]想一想: 為什么不定義最小公約數(shù)和最大公倍數(shù)?,最大公約數(shù)的性質(zhì),GCD: Greatest Common Divisor把a, b寫成素數(shù)分解式則(a,b)的公式為,最大公約數(shù)的性質(zhì),知道了最大公約數(shù)a, b，經(jīng)常把a和b寫為a=

5、a1*(a,b), b=b1*(a,b)，則(a1,b1)=1，稱a1和b1互素(relatively prime)GCD滿足分配律(ma,mb)=m(a,b)結(jié)合律(a,b,c)=((a,b),c)=(a,(b,c))冪等律(a,a)=a交換律(a,b)=(b,a)吸收律[a,(a,b)]=a,最大公約數(shù)的性質(zhì),隨機的兩個整數(shù)互素的概率為其中 為黎曼Zeta函數(shù)[Polezzi, 1997](m,n)為從(

6、0,0)到(m,n)的線段（不包含(m,n)）上格點的個數(shù)[Knuth],定理2: gcd(a,b)*lcm(a,b)=a*b,使用惟一分解定理. 設(shè)則有:容易驗證定理成立,,,,例題：除法表達式,除法表達式有如下的形式：X1 / X2 / X3 / … / Xk其中Xi是正整數(shù)且Xi≤109 (k≤10,000)。除法表達式應(yīng)當(dāng)按照從左到右的順序求和，例如表達式1/2/1/2的值為1/4?？梢栽诒磉_式中嵌入括號以改變

7、計算順序，例如表達式(1 / 2) / (1 / 2)的值為1?，F(xiàn)在給一個除法表達式E要求告訴是否可以通過增加括號使表達式值為整數(shù)。,分析,X2必須在分母, 其他都可以在分子最后結(jié)果是整數(shù)嗎？方法一: 把X2分解因數(shù)方法二: 每次約掉X2和Xi的最大公約數(shù)因數(shù)分解是困難的，因此方法二優(yōu),例題：無限賽跑,AB總長度為L車一從A出發(fā)，速度為u車二從B出發(fā)，速度為v走到端點立刻返回，無時間損失開車總時間tu, v, t都是

8、正整數(shù)相遇多少次？,分析,第一種相遇: 相向t?(u+v)=(2k+1)L 第二種相遇: 同向t?|u?v|=(2k+1)L 重復(fù): 在端點相遇第一次同時到達端點時刻為r到達不同端點?到達同一端點A和B分別運動2k1L和(2k2+1)L 下一次到達哪里?不同端點?又同時到達此端點?同時到達另一端點?t=(2k+1)r,分析,如何求r?r是L/u的整數(shù)倍(u*r = k1L)r是L/v的整數(shù)倍r是L/gcd(u,

9、v)的整數(shù)倍u/gcd(u,v) * r/(L/gcd(u,v)) = k1r是滿足條件的最小正數(shù)r=L/gcd(u,v),思考：反素數(shù),正整數(shù)n是一個反素數(shù)，如果這個數(shù)的約數(shù)個數(shù)超過比n小的任何數(shù)的約數(shù)個數(shù)。給定n(<=2*109)，求不超過n的最大反素數(shù)數(shù)m,二、進位制,例題：集裝箱,用若干個盒子（盒子的高度為2的非負整數(shù)次冪）填滿若干個集裝箱（高度也是2的非負整數(shù)次冪），所有盒子的價值和最小盒子和集裝箱的底面全等，

10、因此只需要考慮高度,分析,對于每個尺寸的盒子，按照價值從小到大排序填充a個尺寸為0的集裝箱時只能用尺寸為0的盒子，取最小的a個，剩下的兩兩組合供填充尺寸為1的集裝箱時使用當(dāng)需要填充a個尺寸為k的集裝箱時，選擇尺寸為k的盒子中價值最小的a的，然后把剩下的兩兩組合成尺寸為k+1的供下一次選用時間復(fù)雜度：O(n),例題：反轉(zhuǎn),TOM有9個寄存器a[1]..a[9]，支持以下操作S i j, a[j]?a[i]+1 (i可能等于 j)

11、P i, 輸出a[i]任務(wù): 對于給定n<=255，設(shè)計各個寄存器的初值和一個TOM程序，按順序輸出 n, n-1, n-2, … 0最長的“連續(xù)S操作”片段長度P應(yīng)盡量小,算法一,寄存器i(i<=8)負責(zé)輸出最右的非零位為第i位的數(shù)初始時設(shè)置每個寄存器為此類數(shù)的最大值，寄存器1-8依次為128, 192, 224, 240, 248, 252, 254, 255，寄存器9保持0輸出248(11111000)后，應(yīng)準(zhǔn)

12、備232(11101000)設(shè)置連續(xù)S操作個數(shù)的限制P，每次準(zhǔn)備好一個數(shù)后如果P限制還未達到，應(yīng)該繼續(xù)準(zhǔn)備后面的數(shù)，而不要急著輸出對于n<=255，P限制不大于4,算法二,基本思想：剛執(zhí)行輸出指令的寄存器馬上改考慮4個寄存器的情形，下劃線是輸出值N, N-2, N-5, N-9N-1, N-2, N-5, N-9N-4, N-2, N-5, N-9N-4, N-3, N-5, N-9N-4, N-8, N-5, N

13、-9N-7, N-8, N-5, N-9N-7, N-8, N-6, N-9推廣到9的寄存器，對于N<=44，可得到P=1的解,例題：奇怪的計數(shù)器,用如下方式表示數(shù)：AN-1*2N-1+AN-2*2N-2+ ... +A1×2+A0每個A在范圍0~2內(nèi)。初始時所有的A均為0，要處理M次加2x的操作（每個x不一定都相同），每次最多只允許修改4個A的內(nèi)容。要求模擬這一過程。,分析,多個2連在一起比較“危險”，容

14、易超過4次的限額讓它們之間存在一個0，就緩解了壓力考慮這樣的限制條件任意兩個相鄰的2之間至少有一個0從最低一位2向更低的位數(shù)找，也至少能找到一個0限制條件避免了一次操作需要影響O(N)個二進制位的退化情況，類似于在排序二叉樹中加入了“平衡因子”這個限制。因此不妨稱這個限制條件為“平衡性質(zhì)”。,分析,一開始的0序列滿足平衡性質(zhì)，因此需要構(gòu)造從一個平衡狀態(tài)到另一個平衡狀態(tài)的過渡法則對于增加2i，考察第i位：0，那么0->

15、1，考慮這個0所在的兩個2之間的區(qū)間，如果剩下的都是1（沒有0），那么把區(qū)間最左邊的2進位1，那么1->0，向前一位進1，如果前一位變成2，注意前一位的前面的區(qū)間是否全部都是1，如果那樣也要和1)一樣修改; 如果前一位原來就是2，那么跳轉(zhuǎn)3)2，那么2->1，再將其前面一位加1即可,思考：天平,有一些砝碼, 重量為1, 3, 9, 27, 81…形如3k, 每個重量砝碼只有一個. 任意給一個重量為m的物體, 把它放在天平

16、左邊, 如何把放置砝碼使得天平平衡? 放在左邊或者右邊都可m<=10100,思考：987654321問題,求有多少個n位數(shù)平方以后的末9位為987654321。,思考：奇妙的數(shù),給定n, m，尋找m位n進制數(shù)A，使得2A，3A，…mA的數(shù)字均為A數(shù)字的排列如m=6, n=10時，142,857是唯一解給定數(shù)據(jù)最多只有一組解，也可能無解（如m=6, n=100時）,三、模算術(shù)與方程,歐拉定理,歐拉函數(shù): 1~n中和n互素的元素

17、個數(shù)?(n)Euler定理 若gcd(a, n)=1則a?(n) ?1 (mod n)意義：當(dāng)b很大時ab ?ab mod ?(n)(mod n)，讓指數(shù)一直比較小歐拉函數(shù)是積性函數(shù)，即當(dāng)(m,n)=1時f(mn)=f(m)*f(n),思考：歐拉函數(shù)的計算,給定n，需要多少時間計算?(n)？給定n，需要多少時間計算?(1), ?(2), …, ?(n)的所有值？,例題：模取冪,a, p, m, n均為正整數(shù)，a, p為素數(shù)1&l

18、t;a, p, m, n<65535，且n?2a, n?2p。求：如a=32719, p=54323, m=99, n=65399，則結(jié)果為46184,,例題：模取冪,記f(a,p,m,n)為本題所求的數(shù)，n=1時，任何數(shù)模n都是0，所以f(a,p,m,n)=0，否則a=1時，a的任何次冪都是1，結(jié)果為1 mod n；否則m=0時，結(jié)果為=a mod n；否則n=a時，a的次冪永遠是n的倍數(shù)，結(jié)果為0；否則n=2

19、a時，因為a, p ? 2，如果a中有2的因子，則a的次冪永遠是n的倍數(shù)，結(jié)果為0，否則為a；否則a, n互素，f(a,p,m,n)=af(p,p,m-1,?(n)) mod n，問題轉(zhuǎn)變成求ak mod n，可以二分求解,例題：整數(shù)序列,已知{A1,…,An}、B、P求{X1,…,Xn}使得A1X1+…+AnXn = B(mod P),分析,設(shè)g=(A1,A2,…An,P)，若g不整除B則無解，否則我們可以用遞歸構(gòu)造解：將A1,

20、…An、P和B全部除以g，此時((A1,…An),P)=1，若n=1，則直接求X1使得A1X1 mod P=B；否則設(shè)(A1,…,An-1)=D，則根據(jù)歐幾里德算法一定存在x和y使得ANx + Dy = B(mod p)，可以令Xn=x , 則A1X1+…+An-1Xn-1=B-AnX=Dy(mod p),分析,(A1,…,An-1)=D, 所以(A1,…,An-1,P) = (D,P) | (Dy mod P), 因此完全轉(zhuǎn)化為n

21、-1的情形, 令B=DY mod P即可,四、雜題,例題：Fermat vs Pythagoras,給N(<=100,000)，考慮滿足x2+y2=z2(x<y<z<=N)的三元組求x、y、z互質(zhì)的三元組的個數(shù)和不屬于任何三元組(不光是互質(zhì))的k(k<=N)的個數(shù).例(輸入:輸出)10: 1 4 25: 4 9 100: 16 27,分析,本原三元組一定可以寫成x=uv, y=u2-v2, z=

22、u2+v2, 其中u, v互質(zhì)其他是本原三元組的整數(shù)倍算法預(yù)處理, 保存100,000內(nèi)的所有本原三元組, 以z為關(guān)鍵字排序, d[i]為z<=i的個數(shù), 遞推標(biāo)記它們的倍數(shù)涉及到的數(shù), 按序遞推不屬于任意三元組的個數(shù)g[i]回答詢問是O(1)的, 空間O(n),例題：沒有矩形,n*n的網(wǎng)格, 要求每行每列恰好k個黑點，但任意四個黑點不構(gòu)成邊與坐標(biāo)軸平行的矩形輸入k, 求n=k2-k+1的一個解k<=32且k-

23、1為0, 1或素數(shù),分析,每行用k個數(shù)表示黑色點的列編號, 則不存在矩形當(dāng)且僅當(dāng)任兩行最多一個相同數(shù)構(gòu)造法.第1行涂點1, 2, 3…k以下分k個塊, 每塊有k-1行, 共k2-k+1行第i個塊的第一個點均為i第一個塊的其他點為k+1~k2-k+1其他每個塊的各行為第1個塊的一個平移覆蓋以k=6為例, 第1行和第1個塊(共6行)為:,1 2 3 4 5 61 7 8 9 10 111 12 13 14

24、15 161 17 18 19 20 211 22 23 24 25 261 27 28 29 30 31以k=6為例第一行為1~k, 即1~6每個塊有k-1行, 即5行第i個塊的第一個數(shù)均為i第1個塊的其他點為k+1~k2-k+1即7~31下面開始一行一行構(gòu)造第2個塊,1 2 3 4 5 61 7 8 9 10 111 12 13 14 15 161 17 18 19 20 211 22 23

25、 24 25 261 27 28 29 30 312 7 14 21 23 30第1個數(shù)總是2第2從第1個塊復(fù)制來一個7以后每次從第1個塊的下一行復(fù)制, 源的列號往右偏移2,1 2 3 4 5 61 7 8 9 10 111 12 13 14 15 161 17 18 19 20 211 22 23 24 25 261 27 28 29 30 312 7 14 21 23 302 8 15

26、17 24 31第1個數(shù)還是2這次從8開始復(fù)制相當(dāng)于選取的數(shù)是上一行右移了一個單位(比較黑色和蘭色部分)相當(dāng)于用平移法構(gòu)造k個鏈, 覆蓋塊1的其他數(shù),1 2 3 4 5 61 7 8 9 10 111 12 13 14 15 161 17 18 19 20 211 22 23 24 25 261 27 28 29 30 312 7 14 21 23 302 8 15 17 24 312 9

27、16 18 25 272 10 12 19 26 282 11 13 20 22 293 7 15 18 26 29第3塊還是若干平移鏈, 但間隔變?yōu)?,1 2 3 4 5 61 7 8 9 10 111 12 13 14 15 161 17 18 19 20 211 22 23 24 25 261 27 28 29 30 312 7 14 21 23 302 8 15 17 24 312

28、 9 16 18 25 272 10 12 19 26 282 11 13 20 22 293 7 15 18 26 293 8 16 19 22 30,證明,先證合法性. 每行顯然k個元素, 下面證明每列i也是k個元素ik: i在第1個塊中恰好出現(xiàn)過一次, 其他每塊也恰好出現(xiàn)一次(每一塊的各行是第一塊的一個分解!)，因此一共恰好出現(xiàn)k次下面證明沒有矩形,證明,沒有矩形當(dāng)且僅當(dāng)任意兩行最多只有一個相同的數(shù). 考慮每兩行i