1-數(shù)論初步-全文預(yù)覽
【正文】 4 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個(gè)數(shù)還是 2 ? 這次從 8開始復(fù)制 ? 相當(dāng)于選取的數(shù)是上一行右移了一個(gè)單位 (比較黑色和蘭色部分 ) ? 相當(dāng)于用 平移法 構(gòu)造 k個(gè)鏈 , 覆蓋 塊 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個(gè)元素 , 下面證明每列 i也是 k個(gè)元素 – i=k: 考慮第 1行和塊 i的 k1行 – ik: i在第 1個(gè)塊中恰好出現(xiàn)過一次 , 其他每塊也恰好出現(xiàn)一次 (每一塊的各行是第一塊的一個(gè)分解 !)，因此一共恰好出現(xiàn) k次 ? 下面證明沒有矩形 證明 ? 沒有矩形當(dāng)且僅當(dāng)任意兩行最多只有一個(gè)相同的數(shù) . 考慮每?jī)尚?i, j, 規(guī)定 ij –若 i=1, j只有第 1個(gè)數(shù)字出現(xiàn)在第一行 –若 i和 j在同一個(gè)塊內(nèi) , 則只有第 1個(gè)數(shù)相同 –若 i和 j屬于不同的兩塊 , 則第 1個(gè)數(shù)不同 , 其他數(shù)來自兩個(gè)間隔不同的鏈 . 因?yàn)?k1是素?cái)?shù)或 0, 1, 所以此二鏈不可能有兩個(gè)公共元素 。 如果前一位原來就是 2，那么跳轉(zhuǎn) 3) – 2，那么 21，再將其前面一位加 1即可 思考：天平 ? 有一些砝碼 , 重量為 1, 3, 9, 27, 81… 形如 3k, 每個(gè)重量砝碼只有一個(gè) . 任意給一個(gè)重量為m的物體 , 把它放在天平左邊 , 如何把放置砝碼使得天平平衡 ? 放在左邊或者右邊都可 ? m=10100 思考： 987654321問題 ? 求有多少個(gè) n位數(shù)平方以后的末 9位為987654321。 ? 要求模擬這一過程。 分析 ? X2必須在分母 , 其他都可以在分子 ? 最后結(jié)果是整數(shù)嗎？ –方法一 : 把 X2分解因數(shù) –方法二 : 每次約掉 X2和 Xi的最大公約數(shù) ? 因數(shù)分解是困難的，因此方法二優(yōu) 例題：無(wú)限賽跑 ? AB總長(zhǎng)度為 L – 車一從 A出發(fā)，速度為 u – 車二從 B出發(fā)，速度為 v ? 走到端點(diǎn)立刻返回，無(wú)時(shí)間損失 ? 開車總時(shí)間 t ? u, v, t都是正整數(shù) ? 相遇多少次？ 分析 ? 第一種相遇 : 相向 t?(u+v)=(2k+1)L ? 第二種相遇 : 同向 t?|u?v|=(2k+1)L ? 重復(fù) : 在端點(diǎn)相遇 ? 第一次同時(shí)到達(dá)端點(diǎn)時(shí)刻為 r –到達(dá)不同端點(diǎn) ? –到達(dá)同一端點(diǎn) ? A和 B分別運(yùn)動(dòng) 2k1L和 (2k2+1)L –下一次到達(dá)哪里 ? ? 不同端點(diǎn) ?又同時(shí)到達(dá)此端點(diǎn) ?同時(shí)到達(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)) = k1 – r是滿足條件的最小正數(shù) – r=L/gcd(u,v) 問題 4: 分解因數(shù) ? 分解因數(shù)可以轉(zhuǎn)換為求最小素因子 (找到最小素因子后遞歸求解 ) ? 分解素因數(shù)后得到惟一分解式 sum{piki}, 可以求出約數(shù)個(gè)數(shù) , 即所有 ki+1的乘積 (由乘法原理容易證明 ) ? 方法一 : 試除法 ? 方法二 : pollardrho算法 思考：反素?cái)?shù) ? 正整數(shù) n是一個(gè)反素?cái)?shù)，如果這個(gè)數(shù)的約數(shù)個(gè)數(shù)超過比 n小的任何數(shù)的約數(shù)個(gè)數(shù)。 例題：除法表達(dá)式 ? 除法表達(dá)式有如下的形式： ? X1 / X2 / X3 / … / Xk ? 其中 Xi是正整數(shù)且 Xi≤109 (k≤10,000)。 x = y。 y = 0。求 K的最大值，使得第一個(gè)人重新拿到球之前，每個(gè)人都拿過球。可以列出一個(gè)關(guān)于 x[i](1=i=m)的位
化學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1