1-數(shù)論初步(文件)
【正文】 關(guān)鍵 : 求 abmod n – a, a2, a4, a8, a16, … – 同余方程可以做乘法， b做二進(jìn)制展開(kāi)選擇 ? 方法二：擴(kuò)展的 Euclid算法 – 存在整數(shù) y，使得 axny=b – 記 d=(a,n)， a’=a/d, n’=n/d，必須有 d|b – a’xn’y=1*(b/d) – 注意： x不唯一 , 所有 x相差 n/d的整數(shù)倍 中國(guó)剩余定理 ? 考慮方程組 x≡ai(mod mi), mi兩兩互素 ? 在 0=xM=m1m2…m k內(nèi)有唯一解 ? 記 Mi=M/mi，則 (Mi,mi)=1 –存在 pi,qi， Mipi+miqi=1 –記錄 ei=Mipi， 則 ? j=i時(shí) ei≡1(mod mj) ? ji時(shí) ei≡0(mod mj) –則 e1a1+e2a2+…+e kak就是一個(gè)解 , 調(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ó)剩余定理 ? 其他規(guī)則同余方程 –二項(xiàng)方程 : 借助離散對(duì)數(shù) (本身 ??) –高次方程 : 分解 n, 降冪 –單個(gè)多變?cè)€性方程 : 消法 例題：整數(shù)序列 ? 已知 {A1,…,A n}、 B、 P求 {X1,…,X n}使得 ? A1X1+…+A nXn = B(mod P) 分析 ? 設(shè) g=(A1,A2,…A n,P)，若 g不整除 B則無(wú)解，否則我們可以用遞歸構(gòu)造解： –將 A1,…A n、 P和 B全部除以 g，此時(shí)((A1,…A n),P)=1， –若 n=1，則直接求 X1使得 A1X1 mod P=B；否則 –設(shè) (A1,…,A n1)=D，則根據(jù)歐幾里德算法一定存在 x和 y使得 ANx + Dy = B(mod p)，可以令Xn=x , 則 A1X1+…+A n1Xn1=BAnX=Dy(mod p) 分析 ? (A1,…,A n1)=D, 所以 (A1,…,A n1,P) = (D,P) | (Dy mod P), 因此完全轉(zhuǎn)化為 n1的情形 , 令B=DY mod P即可 四、雜題 例題： Fermat vs Pythagoras ? 給 N(=100,000)，考慮滿足 x2+y2=z2(xyz=N)的三元組 ? 求 x、 y、 z互質(zhì)的三元組的個(gè)數(shù)和不屬于任何三元組 (不光是互質(zhì) )的 k(k=N)的個(gè)數(shù) . ? 例 (輸入 :輸出 ) – 10: 1 4 – 25: 4 9 – 100: 16 27 分析 ? 本原三元組一定可以寫(xiě)成 x=uv, y=u2v2, z=u2+v2, 其中 u, v互質(zhì) ? 其他是本原三元組的整數(shù)倍 ? 算法 –預(yù)處理 , 保存 100,000內(nèi)的所有本原三元組 , 以 z為關(guān)鍵字排序 , d[i]為 z=i的個(gè)數(shù) , 遞推 –標(biāo)記它們的倍數(shù)涉及到的數(shù) , 按序遞推不屬于任意三元組的個(gè)數(shù) g[i] –回答詢問(wèn)是 O(1)的 , 空間 O(n) 例題：沒(méi)有矩形 ? n*n的網(wǎng)格 , 要求每行每列恰好 k個(gè)黑點(diǎn)，但任意四個(gè)黑點(diǎn)不構(gòu)成矩形 ? 輸入 k, 求 n=k2k+1的一個(gè)解 ? k=32且 k1為 0, 1或素?cái)?shù) 分析 ? 每行用 k個(gè)數(shù)表示黑色點(diǎn)的列編號(hào) , 則不存在矩形當(dāng)且僅當(dāng)任兩行最多一個(gè)相同數(shù) ? 構(gòu)造法 . – 第 1行涂點(diǎn) 1, 2, 3…k – 以下分 k個(gè)塊 , 每塊有 k1行 , 共 k2k+1行 – 第 i個(gè)塊的一個(gè)點(diǎn)均為 i – 第一個(gè)塊的其他點(diǎn)為 k+1~k2k+1 – 其他每個(gè)塊的各行為第 1個(gè)塊的一個(gè) 平移覆蓋 ? 以 k=6為例 , 第 1行和第 1個(gè)塊 (共 6行 )為 : 1 2 3 4 5 6 1 7 8 9 10 11 1 12 13 14 15 16 1 17 18 19 20 21 1 22 23 24 25 26 1 27 28 29 30 31 ? 以 k=6為例 ? 第一行為 1~k, 即 1~6 ? 每個(gè)塊有 k1行 , 即 5行 ? 第 i個(gè)塊的第一個(gè)數(shù)均為 i ? 第 1個(gè)塊的其他點(diǎn)為 k+1~k2k+1即 7~31 ? 下面開(kāi)始一行一行構(gòu)造第 2個(gè)塊 1 2 3 4 5 6 1 7 8 9 10 11 1 12 13 14 15 16 1 17 18 19 20 21 1 22 23 24 25 26 1 27 28 29 30 31 2 7 14 21 23 30 ? 第 1個(gè)數(shù)總是 2 ? 第 2從第 1個(gè)塊復(fù)制來(lái)一個(gè) 7 ? 以后每次從第 1個(gè)塊的下一行復(fù)制 , 源的列號(hào)往右偏移 2 1 2 3 4 5 6 1 7 8 9 10 11 1 12 13 1
化學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1