劉汝佳-1數(shù)論初步

1、2005年浙江省隊(duì)培訓(xùn)第1講 數(shù)論初步,劉汝佳,目錄,一、基本概念二、進(jìn)位制三、模算術(shù)與方程四、雜題,一、基本概念,基本概念,整除與約數(shù)、倍數(shù). 注意負(fù)數(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), 是一個格,素數(shù)和合數(shù),如果大于1的正整數(shù)p僅有的正因子是1和p, 則稱p為

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

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),同余,為什么有同余?13241234…1+432435..2=24….7余數(shù)可以作為原數(shù)的一個signature(標(biāo)記).如果標(biāo)記下的運(yùn)算錯誤,

4、 一定錯誤如果標(biāo)記下的運(yùn)算正確?,最大公約數(shù)和最小公倍數(shù),令a和b是不全為0的兩個整數(shù)，能使d|a和d|b的最大整數(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] 定理: ab = gcd(a,b) * lcm(a,b),定理的證明,使用惟一分解定理. 設(shè)則有:容易驗(yàn)證定理成立

5、,,,,例題：佳佳的困惑,給出一個數(shù)N，含數(shù)字1、2、3、4，把N的所有數(shù)字重新排列一下組成一個新數(shù)，使它是7的倍數(shù)。,分析,把數(shù)字1、2、3、4從中抽出，然后把其他數(shù)字按照原順序排列（事實(shí)上，怎么排列都無所謂）組成自然數(shù)ww*10,000整除7取余有7種可能，即是為0、1、2、3、4、5、6。這時如果能用數(shù)字1、2、3、4排列出7個數(shù)，使它們整除7取余的值分別為0、1、2、3、4、5、6，把這個4位數(shù)接在w后面即為問題的解。,例題：

6、街道數(shù),找所有的(n, k), 滿足:1+2+..+(n-1)=(n+1)+(n+2)…+k輸出按k排序的前10個,分析,整理得: n(n-1)=(k-n)(n+k+1)化簡得: k2+k-2n2=0, 即n2=k(k+1)/2由于k和k+1互素, 因此要么k是完全平方數(shù)要么k/2是完全平方數(shù)分別設(shè)k=m2和2m2, 枚舉m,例題：齒輪,假設(shè)有三種齒輪：6齒，12齒，30齒。想要實(shí)現(xiàn)4 : 5的比例，一種可行方案如下：

7、給定可用的齒輪（每種均有無窮多），設(shè)計一系列傳輸c1 : d1, c2 : d2, …, cm : dm，使得其綜合比例(c1c2c3…cm)/(d1d2d3…dm)為給定值a:b。給定齒輪的齒數(shù)為5到100，a和b不超過10000。,分析,使用惟一分解定理, 單獨(dú)考慮各個素因子c1 = p1a1*p2*a2*…c2 = p1b1*p2*b2*……則c1x*c2y=p1(x*a1+y*b1) *p2(x*a2+y*b2)

8、目標(biāo)a:b = p1z1 * p2z2 …x*a1+y*b1=z1; x*a2+y*b2=z2,分析,第i個齒輪的使用情況用xi表示，xi>0表示用在分子xi次，xi<0表示用在分母-xi次。由于ai<=100，只需要考慮100以內(nèi)的25個素數(shù)考慮每個素數(shù)pi的指數(shù)，可以構(gòu)造一個線性方程，共25個等式分子分母個數(shù)相等，故所有xi的和為0，消元后枚舉獨(dú)立變量,例題：破解RSA,給定M個數(shù)，它們的質(zhì)因子在前T個

9、質(zhì)數(shù)范圍內(nèi)。求這M個數(shù)組成集合的滿足如下條件的非空子集個數(shù)：子集中所有數(shù)的積為完全平方數(shù)。,分析,首先將讀入的M個數(shù)，分解質(zhì)因數(shù)，并對每個質(zhì)因數(shù)出現(xiàn)次數(shù)的奇偶性進(jìn)行記錄。設(shè)x[i]=0或1代表是否使用第i個數(shù)。可以列出一個關(guān)于x[i](1<=i<=m)的位方程組（乘積的所有質(zhì)因數(shù)出現(xiàn)次數(shù)均為偶數(shù)）。解該方程組，檢查最后有多少自變量，設(shè)有n個，那么結(jié)果應(yīng)該是2n-1（除去空集）。 時空復(fù)雜度均為O(M2),思考：傳球游戲,

10、N個人圍圈玩?zhèn)髑蛴螒颍_始時第一個人拿著球，每個人把球傳給左手的第K個人。滿足1≤K≤N/2。求K的最大值，使得第一個人重新拿到球之前，每個人都拿過球。,基本問題,如何求1~n的所有素數(shù)?如何判斷一個數(shù)n是否為素數(shù)?如何求兩個數(shù)的最大公約數(shù)?如何給一個數(shù)n分解素因數(shù)?,問題1: 1~n的素數(shù),假設(shè)要求1~100的素數(shù)2是素數(shù), 刪除2*2, 2*3, 2*4, …, 2*50第一個沒被刪除的是3, 刪除3*3, 3*4, 3*

11、5,…,3*33第一個沒被刪除的是5, 刪除5*5, 5*6, … 5*20得到素數(shù)p時, 需要刪除p*p, p*(p+1), … p*[n/p], 運(yùn)算量為[n/p]-p, 其中p不超過n1/2(想一想, 為什么),Eratosthenes的篩子,小知識 (mathworld.wolfram.com),近似公式(Legendre常數(shù)B=-1.08366),思考：正多邊形,給圓周上n個點(diǎn)的坐標(biāo), 能組成多少個正多邊形？,問題2: 素

12、數(shù)判定,枚舉法: O(n1/2), 指數(shù)級別改進(jìn)的枚舉法: O(phi(n1/2))=O(n1/2/logn), 仍然是指數(shù)級別概率算法: Miller-Rabin測試 + Lucas-Lehmer測試,Miller-Rabin測試,對于奇數(shù)n, 記n=2r*s+1, 其中s為奇數(shù)隨機(jī)選a(1<=a<=n-1), n通過測試的條件是as≡1(mod n), 或者存在0<=j<=r-1使得a2^j*s≡-

13、1(mod n)素數(shù)對于所有a通過測試, 合數(shù)通過測試的概率不超過1/4只測試a=2, 3, 5, 7, 則2.5*1013以內(nèi)唯一一個可以通過所有測試的數(shù)為3215031751,思考：區(qū)間內(nèi)的素數(shù),給出n, m(n<=106, m<=105), 求n~n+m之間的素數(shù)有多少個哪種方法快? 篩還是依次素數(shù)判定?,問題3: 最大公約數(shù),方法一: 使用惟一分解定理, 先分解素因數(shù), 然后求最大公約數(shù)方法二: (Eucli

14、d算法)利用公式gcd(a, b)=gcd(b, a mod b), 時間復(fù)雜度為O(logb)方法三: (二進(jìn)制算法) 若a=b, gcd(a,b)=a, 否則A和b均為偶數(shù), gcd(a,b)=2*gcd(a/2,b/2)A為偶數(shù), b為奇數(shù), gcd(a,b)=gcd(a/2,b)如果a和b均為奇數(shù), gcd(a,b)=gcd(a-b,b)不需要除法, 適合大整數(shù),擴(kuò)展問題,一定存在整數(shù)x,y，使得ax+by=gcd(a

15、,b)int gcd(int a, int b, int&x, int& y){ if(!b){ x = 1; y = 0; return a; } else{ int r = gcd(b, a%b, x, y); t = x; x = y; y = t – a/b*y; return r; }}由數(shù)學(xué)歸納法可證明ax+by=gcd(a,b)滿足ax+by=d的數(shù)對(x,y

16、)不是惟一的, 因?yàn)楫?dāng)x增加b且y減少a時和不變。,例題：除法表達(dá)式,除法表達(dá)式有如下的形式：X1 / X2 / X3 / … / Xk其中Xi是正整數(shù)且Xi≤109 (k≤10,000)。除法表達(dá)式應(yīng)當(dāng)按照從左到右的順序求和，例如表達(dá)式1/2/1/2的值為1/4?？梢栽诒磉_(dá)式中嵌入括號以改變計算順序，例如表達(dá)式(1 / 2) / (1 / 2)的值為1。現(xiàn)在給一個除法表達(dá)式E要求告訴是否可以通過增加括號使表達(dá)式值為整數(shù)。,分析

17、,X2必須在分母, 其他都可以在分子最后結(jié)果是整數(shù)嗎？方法一: 把X2分解因數(shù)方法二: 每次約掉X2和Xi的最大公約數(shù)因數(shù)分解是困難的，因此方法二優(yōu),例題：無限賽跑,AB總長度為L車一從A出發(fā)，速度為u車二從B出發(fā)，速度為v走到端點(diǎn)立刻返回，無時間損失開車總時間tu, v, t都是正整數(shù)相遇多少次？,分析,第一種相遇: 相向t?(u+v)=(2k+1)L 第二種相遇: 同向t?|u?v|=(2k+1)L 重復(fù):

18、在端點(diǎn)相遇第一次同時到達(dá)端點(diǎn)時刻為r到達(dá)不同端點(diǎn)?到達(dá)同一端點(diǎn)A和B分別運(yùn)動2k1L和(2k2+1)L 下一次到達(dá)哪里?不同端點(diǎn)?又同時到達(dá)此端點(diǎn)?同時到達(dá)另一端點(diǎn)?t=(2k+1)r,分析,如何求r?r是L/u的整數(shù)倍(u*r = k1L)r是L/v的整數(shù)倍r是L/gcd(u,v)的整數(shù)倍u/gcd(u,v) * r/(L/gcd(u,v)) = k1r是滿足條件的最小正數(shù)r=L/gcd(u,v),問題4:

19、分解因數(shù),分解因數(shù)可以轉(zhuǎn)換為求最小素因子(找到最小素因子后遞歸求解)分解素因數(shù)后得到惟一分解式sum{piki}, 可以求出約數(shù)個數(shù), 即所有ki+1的乘積(由乘法原理容易證明)方法一: 試除法方法二: pollard-rho算法,思考：反素數(shù),正整數(shù)n是一個反素數(shù)，如果這個數(shù)的約數(shù)個數(shù)超過比n小的任何數(shù)的約數(shù)個數(shù)。給定n(<=2*109)，求不超過n的最大反素數(shù)數(shù)m,二、進(jìn)位制,例題：集裝箱,用若干個盒子（盒子的高度為2

20、的非負(fù)次冪）填滿若干個集裝箱（高度也是2的非負(fù)次冪），使所有盒子的價值和最小。 盒子和集裝箱的底面全等，因此只需要考慮高度,分析,對于每個尺寸的盒子，按照價值從小到大排序填充a的尺寸為0的集裝箱時只能用尺寸為0的盒子，取最小的a個，剩下的兩兩組合供填充尺寸為1的集裝箱時使用當(dāng)需要填充a個尺寸為k的集裝箱時，選擇尺寸為k的盒子中價值最小的a的，然后把剩下的兩兩組合成尺寸為k+1的供下一次選用時間復(fù)雜度：O(n),例題：反轉(zhuǎn),TOM

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

22、, 240, 248, 252, 254, 255，寄存器9保持0輸出248(11111000)后，應(yīng)準(zhǔn)備232(11101000)設(shè)置連續(xù)S操作個數(shù)的限制P，每次準(zhǔn)備好一個數(shù)后如果P限制還未達(dá)到，應(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

23、-4, N-2, N-5, N-9N-4, N-3, N-5, N-9N-4, N-8, N-5, N-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

24、不一定都相同），每次最多只允許修改4個A的內(nèi)容。要求模擬這一過程。,分析,多個2連在一起比較“危險”，容易超過4次的限額讓它們之間存在一個0，就緩解了壓力考慮這樣的限制條件任意兩個相鄰的2之間至少有一個0從最低一位2向更低的位數(shù)找，也至少能找到一個0限制條件避免了一次操作需要影響O(N)個二進(jìn)制位的退化情況，類似于在排序二叉樹中加入了“平衡因子”這個限制。因此不妨稱這個限制條件為“平衡性質(zhì)”。,分析,一開始的0序列滿足平衡性

25、質(zhì)，因此需要構(gòu)造從一個平衡狀態(tài)到另一個平衡狀態(tài)的過渡法則對于增加2i，考察第i位：0，那么0->1，考慮這個0所在的兩個2之間的區(qū)間，如果剩下的都是1（沒有0），那么把區(qū)間最左邊的2進(jìn)位1，那么1->0，向前一位進(jìn)1，如果前一位變成2，注意前一位的前面的區(qū)間是否全部都是1，如果那樣也要和1)一樣修改; 如果前一位原來就是2，那么跳轉(zhuǎn)3)2，那么2->1，再將其前面一位加1即可,思考：天平,有一些砝碼, 重量為1

26、, 3, 9, 27, 81…形如3k, 每個重量砝碼只有一個. 任意給一個重量為m的物體, 把它放在天平左邊, 如何把放置砝碼使得天平平衡? 放在左邊或者右邊都可m<=10100,思考：987654321問題,求有多少個n位數(shù)平方以后的末9位為987654321。,思考：奇妙的數(shù),給定n, m，尋找m位n進(jìn)制數(shù)A，使得2A，3A，…mA的數(shù)字均為A數(shù)字的排列如m=6, n=10時，142,857是唯一解給定數(shù)據(jù)最多只有一組

27、解，也可能無解（如m=6, n=100時）,三、模算術(shù)與方程,歐拉定理,歐拉函數(shù): 1~n中和n互素的元素個數(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),

28、 ?(2), …, ?(n)的所有值？,例題：模取冪,a, p, m, n均為正整數(shù)，a, p為素數(shù)1<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

29、n；否則m=0時，結(jié)果為=a mod n；否則n=a時，a的次冪永遠(yuǎn)是n的倍數(shù)，結(jié)果為0；否則n=2a時，因?yàn)閍, p ? 2，如果a中有2的因子，則a的次冪永遠(yuǎn)是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，可以二分求解,線性同余方程,ax≡b(mod n)方法一：利用Euler函數(shù)a*a?(n)-1 ?1 ?a(b*a?(

30、n)-1) ?b關(guān)鍵: 求abmod na, a2, a4, a8, a16, …同余方程可以做乘法，b做二進(jìn)制展開選擇方法二：擴(kuò)展的Euclid算法存在整數(shù)y，使得ax-ny=b 記d=(a,n)，a’=a/d, n’=n/d，必須有d|ba’x-n’y=1*(b/d)注意：x不唯一, 所有x相差n/d的整數(shù)倍,中國剩余定理,考慮方程組x≡ai(mod mi), mi兩兩互素在0i時ei≡0(mod mj)則e1a

31、1+e2a2+…+ekak就是一個解, 調(diào)整得到[0,m)內(nèi)的唯一解（想一想，如何調(diào)整）,整理一下,一般線性方程組aixi≡bi(mod ni)ax≡b(mod n) ? x≡b1(mod n1)x≡b1(mod n1) ? x≡b1(mod p1,i)用中國剩余定理其他規(guī)則同余方程二項(xiàng)方程: 借助離散對數(shù)(本身??)高次方程: 分解n, 降冪單個多變元線性方程: 消法,例題：整數(shù)序列,已知{A1,…,An}、B、P求{X

32、1,…,Xn}使得A1X1+…+AnXn = B(mod P),分析,設(shè)g=(A1,A2,…An,P)，若g不整除B則無解，否則我們可以用遞歸構(gòu)造解：將A1,…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

33、=B-AnX=Dy(mod p),分析,(A1,…,An-1)=D, 所以(A1,…,An-1,P) = (D,P) | (Dy mod P), 因此完全轉(zhuǎn)化為n-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&

34、lt;=N)的個數(shù).例(輸入:輸出)10: 1 4 25: 4 9 100: 16 27,分析,本原三元組一定可以寫成x=uv, y=u2-v2, z=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)

35、,例題：沒有矩形,n*n的網(wǎng)格, 要求每行每列恰好k個黑點(diǎn)，但任意四個黑點(diǎn)不構(gòu)成矩形輸入k, 求n=k2-k+1的一個解k<=32且k-1為0, 1或素數(shù),分析,每行用k個數(shù)表示黑色點(diǎn)的列編號, 則不存在矩形當(dāng)且僅當(dāng)任兩行最多一個相同數(shù)構(gòu)造法.第1行涂點(diǎn)1, 2, 3…k以下分k個塊, 每塊有k-1行, 共k2-k+1行第i個塊的一個點(diǎn)均為i第一個塊的其他點(diǎn)為k+1~k2-k+1其他每個塊的各行為第1個塊的一個平移

36、覆蓋以k=6為例, 第1行和第1個塊(共6行)為:,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 31以k=6為例第一行為1~k, 即1~6每個塊有k-1行, 即5行第i個塊的第一個數(shù)均為i第1個塊的其他點(diǎn)為k+1~k2-k+1即7~31下面開始一行一行構(gòu)造第2個塊,1

37、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 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

38、 18 19 20 211 22 23 24 25 261 27 28 29 30 312 7 14 21 23 302 8 15 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

39、 22 23 24 25 261 27 28 29 30 312 7 14 21 23 302 8 15 17 24 312 9 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 2

40、11 22 23 24 25 261 27 28 29 30 312 7 14 21 23 302 8 15 17 24 312 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)一次