1-數(shù)論初步-文庫吧
2025-07-09 03:07 本頁面
【正文】 以內(nèi)的 25個(gè)素?cái)?shù) ? 考慮每個(gè)素?cái)?shù) pi的指數(shù)，可以構(gòu)造一個(gè)線性方程，共 25個(gè)等式 ? 分子分母?jìng)€(gè)數(shù)相等，故所有 xi的和為 0， ? 消元后枚舉獨(dú)立變量 例題：破解 RSA ? 給定 M個(gè)數(shù)，它們的質(zhì)因子在前 T個(gè)質(zhì)數(shù)范圍內(nèi)。求這 M個(gè)數(shù)組成集合的滿足如下條件的非空子集個(gè)數(shù)：子集中所有數(shù)的積為完全平方數(shù)。 分析 ? 首先將讀入的 M個(gè)數(shù)，分解質(zhì)因數(shù)，并對(duì)每個(gè)質(zhì)因數(shù)出現(xiàn)次數(shù)的奇偶性進(jìn)行記錄。 ? 設(shè) x[i]=0或 1代表是否使用第 i個(gè)數(shù)?？梢粤谐鲆粋€(gè)關(guān)于 x[i](1=i=m)的位方程組（乘積的所有質(zhì)因數(shù)出現(xiàn)次數(shù)均為偶數(shù)）。 ? 解該方程組，檢查最后有多少自變量，設(shè)有 n個(gè)，那么結(jié)果應(yīng)該是 2n1（除去空集）。 時(shí)空復(fù)雜度均為 O(M2) 思考：傳球游戲 ? N個(gè)人圍圈玩?zhèn)髑蛴螒?，開始時(shí)第一個(gè)人拿著球，每個(gè)人把球傳給左手的第 K個(gè)人。滿足 1≤K≤N/2。求 K的最大值，使得第一個(gè)人重新拿到球之前，每個(gè)人都拿過球。 基本問題 ? 如何求 1~n的所有素?cái)?shù) ? ? 如何判斷一個(gè)數(shù) n是否為素?cái)?shù) ? ? 如何求兩個(gè)數(shù)的最大公約數(shù) ? ? 如何給一個(gè)數(shù) n分解素因數(shù) ? 問題 1: 1~n的素?cái)?shù) ? 假設(shè)要求 1~100的素?cái)?shù) – 2是素?cái)?shù) , 刪除 2*2, 2*3, 2*4, …, 2*50 –第一個(gè)沒被刪除的是 3, 刪除 3*3, 3*4, 3*5,…,3*33 –第一個(gè)沒被刪除的是 5, 刪除 5*5, 5*6, … 5*20 ? 得到素?cái)?shù) p時(shí) , 需要?jiǎng)h除 p*p, p*(p+1), … p*[n/p], 運(yùn)算量為 [n/p]p, 其中 p不超過n1/2(想一想 , 為什么 ) Eratosthenes的篩子 小知識(shí) () ? 近似公式 (Legendre常數(shù) B=) 思考：正多邊形 ? 給圓周上 n個(gè)點(diǎn)的坐標(biāo) , 能組成多少個(gè)正多邊形？ 問題 2: 素?cái)?shù)判定 ? 枚舉法 : O(n1/2), 指數(shù)級(jí)別 ? 改進(jìn)的枚舉法 : O(phi(n1/2))=O(n1/2/logn), 仍然是指數(shù)級(jí)別 ? 概率算法 : MillerRabin測(cè)試 + LucasLehmer測(cè)試 MillerRabin測(cè)試 ? 對(duì)于奇數(shù) n, 記 n=2r*s+1, 其中 s為奇數(shù) ? 隨機(jī)選 a(1=a=n1), n通過測(cè)試的條件是 – as≡1(mod n), 或者 –存在 0=j=r1使得 a2^j*s≡1(mod n) ? 素?cái)?shù)對(duì)于所有 a通過測(cè)試 , 合數(shù)通過測(cè)試的概率不超過 1/4 ? 只測(cè)試 a=2, 3, 5, 7, 則 *1013以內(nèi)唯一一個(gè)可以通過所有測(cè)試的數(shù)為 3215031751 思考：區(qū)間內(nèi)的素?cái)?shù) ? 給出 n, m(n=106, m=105), 求 n~n+m之間的素?cái)?shù)有多少個(gè) ? 哪種方法快 ? 篩還是依次素?cái)?shù)判定 ? 問題 3: 最大公約數(shù) ? 方法一 : 使用惟一分解定理 , 先分解素因數(shù) , 然后求最大公約數(shù) ? 方法二 : (Euclid算法 )利用公式 gcd(a, b)=gcd(b, a mod b), 時(shí)間復(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(ab,b) ? 不需要除法 , 適合大整數(shù) 擴(kuò)展問題 ? 一定存在整數(shù) x,y，使得 ax+by=gcd(a,b) int gcd(int a, int b, intamp。x, intamp。 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ù)對(duì) (x,y)不是惟一的 , 因?yàn)楫?dāng) x增加 b且 y減少 a時(shí)和不變。 例題：除法表達(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á)式中嵌入括號(hào)以改變計(jì)算順序，例如表達(dá)式 (1 / 2) / (1 / 2)的值為 1。 ? 現(xiàn)在給一個(gè)除法表達(dá)式 E要求告訴是否可以通過增加括號(hào)使表達(dá)式值為整數(shù)。 分析 ? X2必須在分母 , 其他都可以在分子 ? 最后結(jié)果是整數(shù)嗎？ –方法一 : 把 X2分解因數(shù) –方法二 : 每次約掉 X2和 Xi的最大公約數(shù) ? 因數(shù)分解是
化學(xué)相關(guān)推薦
鄂ICP備17016276號(hào)-1