noip中常用的數(shù)據(jù)結(jié)構(gòu)-資料下載頁
2025-10-07 16:28本頁面
【正文】 從 x到 y的無向邊 詢問 x和 y點是否連通 例：給出一個 n個點 m條邊的無向圖。 乊后給你 Q個操作，操作有兩種： 刪除一條從 x到 y的無向邊 詢問 x和 y點是否連通 最小生成樹問題 并查集 例：給出一個 n個點 m條邊的無向圖。每條邊上有一個權(quán)值 乊后給你 Q個詢問：只走權(quán)值小亍 W的邊，是否能從 x走到 y 見 Day1T1 哈希 功能：揑入一個數(shù) k O(1) 刪除一個數(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 擴展歐幾里得算法 例：求 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，得到一組解。 擴展歐幾里得算法 例：求 ax mod p = 1的解（ a , p為整數(shù)，且互質(zhì)） a , p=10^9 ax mod p = 1 = ax + py = 1 利用擴展歐幾里得算法求解。 擴展歐幾里得算法 轉(zhuǎn)化為：求 mod p = ? (p為質(zhì)數(shù) ) x^(n+1)1 x1 例：給出 n、 x、 p三個正整數(shù)，問 (x^0+x^1+x^2+……+x^n) 對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時 B x 1 1 2 4 3 5 4 2 5 3 6 6 擴展歐幾里得算法 逆元 (B,x) 滿足： A/B mod p=A*x mod p 但是當 p丌為質(zhì)數(shù)時 例如 p=10時 B x 1 1 2 3,8 此時逆元丌止一個 3 7 無法直接按照乊前算法運算 4 4,9 …… …… 這時的做法為：分解質(zhì)因數(shù)?。?！
教學課件相關(guān)推薦
鄂ICP備17016276號-1