1-數(shù)論初步-資料下載頁
2025-07-24 03:07本頁面
【正文】 P即可 四、雜題 例題： Fermat vs Pythagoras ? 給 N(=100,000)，考慮滿足 x2+y2=z2(xyz=N)的三元組 ? 求 x、 y、 z互質的三元組的個數(shù)和不屬于任何三元組 (不光是互質 )的 k(k=N)的個數(shù) . ? 例 (輸入 :輸出 ) – 10: 1 4 – 25: 4 9 – 100: 16 27 分析 ? 本原三元組一定可以寫成 x=uv, y=u2v2, z=u2+v2, 其中 u, v互質 ? 其他是本原三元組的整數(shù)倍 ? 算法 –預處理 , 保存 100,000內的所有本原三元組 , 以 z為關鍵字排序 , d[i]為 z=i的個數(shù) , 遞推 –標記它們的倍數(shù)涉及到的數(shù) , 按序遞推不屬于任意三元組的個數(shù) g[i] –回答詢問是 O(1)的 , 空間 O(n) 例題：沒有矩形 ? n*n的網(wǎng)格 , 要求每行每列恰好 k個黑點，但任意四個黑點不構成矩形 ? 輸入 k, 求 n=k2k+1的一個解 ? k=32且 k1為 0, 1或素數(shù) 分析 ? 每行用 k個數(shù)表示黑色點的列編號 , 則不存在矩形當且僅當任兩行最多一個相同數(shù) ? 構造法 . – 第 1行涂點 1, 2, 3…k – 以下分 k個塊 , 每塊有 k1行 , 共 k2k+1行 – 第 i個塊的一個點均為 i – 第一個塊的其他點為 k+1~k2k+1 – 其他每個塊的各行為第 1個塊的一個 平移覆蓋 ? 以 k=6為例 , 第 1行和第 1個塊 (共 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 ? 每個塊有 k1行 , 即 5行 ? 第 i個塊的第一個數(shù)均為 i ? 第 1個塊的其他點為 k+1~k2k+1即 7~31 ? 下面開始一行一行構造第 2個塊 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個數(shù)總是 2 ? 第 2從第 1個塊復制來一個 7 ? 以后每次從第 1個塊的下一行復制 , 源的列號往右偏移 2 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 2 8 15 17 24 31 ? 第 1個數(shù)還是 2 ? 這次從 8開始復制 ? 相當于選取的數(shù)是上一行右移了一個單位 (比較黑色和蘭色部分 ) ? 相當于用 平移法 構造 k個鏈 , 覆蓋 塊 1的其他數(shù) 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 2 8 15 17 24 31 2 9 16 18 25 27 2 10 12 19 26 28 2 11 13 20 22 29 3 7 15 18 26 29 ? 第 3塊還是若干平移鏈 , 但間隔變?yōu)?3 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 2 8 15 17 24 31 2 9 16 18 25 27 2 10 12 19 26 28 2 11 13 20 22 29 3 7 15 18 26 29 3 8 16 19 22 30 證明 ? 先證合法性 . 每行顯然 k個元素 , 下面證明每列 i也是 k個元素 – i=k: 考慮第 1行和塊 i的 k1行 – ik: i在第 1個塊中恰好出現(xiàn)過一次 , 其他每塊也恰好出現(xiàn)一次 (每一塊的各行是第一塊的一個分解 !)，因此一共恰好出現(xiàn) k次 ? 下面證明沒有矩形 證明 ? 沒有矩形當且僅當任意兩行最多只有一個相同的數(shù) . 考慮每兩行 i, j, 規(guī)定 ij –若 i=1, j只有第 1個數(shù)字出現(xiàn)在第一行 –若 i和 j在同一個塊內 , 則只有第 1個數(shù)相同 –若 i和 j屬于不同的兩塊 , 則第 1個數(shù)不同 , 其他數(shù)來自兩個間隔不同的鏈 . 因為 k1是素數(shù)或 0, 1, 所以此二鏈不可能有兩個公共元素
化學相關推薦
鄂ICP備17016276號-1