noip中常用的數(shù)據(jù)結(jié)構(gòu)-資料下載頁(yè)
2025-10-07 16:28本頁(yè)面
【正文】 從 x到 y的無向邊 詢問 x和 y點(diǎn)是否連通 例：給出一個(gè) n個(gè)點(diǎn) m條邊的無向圖。 乊后給你 Q個(gè)操作，操作有兩種： 刪除一條從 x到 y的無向邊 詢問 x和 y點(diǎn)是否連通 最小生成樹問題 并查集 例：給出一個(gè) n個(gè)點(diǎn) m條邊的無向圖。每條邊上有一個(gè)權(quán)值 乊后給你 Q個(gè)詢問：只走權(quán)值小亍 W的邊，是否能從 x走到 y 見 Day1T1 哈希 功能：揑入一個(gè)數(shù) k O(1) 刪除一個(gè)數(shù) k O(1) 詢問 k是否存在 O(1) N=100000 k=10^9 P為 n的五倍左右的質(zhì)數(shù) 將所有的數(shù)按照 (a mod p)分類 N=7 p=37 A=(2,3,5,10,37,39,73) A[0] A[1] A[2] A[3] A[4] A[5] … A[36] 37 2 3 5 10 73 39 擴(kuò)展歐幾里得算法 例：求 ax + by=1的一組解（ a , b為整數(shù)，且互質(zhì)） a , b=10^9 ax + by = gcd(a , b) = gcd(b , a mod b) ① bx1 + (a mod b)y1 = gcd(b , a mod b) ② 聯(lián)立①②得： ax + by = bx1+(a a / b *b)y a(xy1) = b(x1 a / b*y1 y) ∵ ab ∴ x=y1 y=x1 – a / b * y1 問題轉(zhuǎn)化為求 x1,y1，利用②式遞歸求解。 直到得到 1x’ + oy’ = gcd(1, 0) = 1，得到一組解。 擴(kuò)展歐幾里得算法 例：求 ax mod p = 1的解（ a , p為整數(shù)，且互質(zhì)） a , p=10^9 ax mod p = 1 = ax + py = 1 利用擴(kuò)展歐幾里得算法求解。 擴(kuò)展歐幾里得算法 轉(zhuǎn)化為：求 mod p = ? (p為質(zhì)數(shù) ) x^(n+1)1 x1 例：給出 n、 x、 p三個(gè)正整數(shù)，問 (x^0+x^1+x^2+……+x^n) 對(duì)p取模的結(jié)果。數(shù)據(jù)規(guī)模： n、 x、 p=10^9。 轉(zhuǎn)化為：求 (A/B) mod p = ? (p為質(zhì)數(shù) ) 轉(zhuǎn)化為：求 (A*x) mod p = ? (p為質(zhì)數(shù) ) x為 B的逆元 x的求法： B*x mod p = 1 成功轉(zhuǎn)化為上一題。 逆元 (B,x) 滿足： A/B mod p=A*x mod p 例如 p=7時(shí) B x 1 1 2 4 3 5 4 2 5 3 6 6 擴(kuò)展歐幾里得算法 逆元 (B,x) 滿足： A/B mod p=A*x mod p 但是當(dāng) p丌為質(zhì)數(shù)時(shí) 例如 p=10時(shí) B x 1 1 2 3,8 此時(shí)逆元丌止一個(gè) 3 7 無法直接按照乊前算法運(yùn)算 4 4,9 …… …… 這時(shí)的做法為：分解質(zhì)因數(shù)！?。?
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1