【正文】 ads // 和2409 一樣 * 強(qiáng)烈推薦：（這題很不錯哦，很巧妙） pku2888 Magic Bracelet // [i][j] 為可達(dá)矩陣. 而且注意約數(shù)的個數(shù)范圍。其中矩陣的冪可以預(yù)先求出所有matrix[2^i] 出來，然后根據(jù)二進(jìn)制來 求。 2. 置換，置換的運(yùn)算 置換的概念還是比較好理解的，《組合數(shù)學(xué)》里面有講。對于置換的冪運(yùn)算大家可以參考一下潘震皓的那篇《置換群快速冪運(yùn)算研究與探討》，寫的很好。 * 簡單題：（應(yīng)該理解概念就可以了） pku3270 Cow Sorting // 列出置換，然后對于每一個置換循環(huán)，不斷用環(huán)中的最小的那個和其他的進(jìn)行換位，可以得到最優(yōu)。另外還有一種情況就是用整個置換最小的那個和該環(huán)進(jìn)行換位，對于每個環(huán)求出這兩個的最小值加起來就可以了。 pku1026 Cipher // 先找出所有置換循環(huán)，然后對于每一位來計算k% 循環(huán)長度后對應(yīng)于哪個位置,O(n) 復(fù)雜度。注意讀寫方面的東西。 * 置換冪運(yùn)算： pku1721 CARDS // 詳細(xì)見05 集訓(xùn)隊(duì)論文《置換群快速冪運(yùn)算研究與探討》。 pku3128 Leonardo39。s Notebook// 摘自： 題目意思是：一個置換是否可以由另一個置換的平方得來的。一個置換的平方，原來偶數(shù)長的循環(huán)會被分裂成兩段長度相等的循環(huán)，而奇數(shù)長的循環(huán)不會被分裂。題目只是問是否存在，所以只要看所給置換中偶數(shù)長的循環(huán)是否成對，否則就不能由一個置換的平方得來。 補(bǔ)充：因?yàn)槿绻o置換的循環(huán)是偶數(shù)，則肯定是由分裂過來的，那么一定是成對的，否則如果是奇數(shù)，那么有可能是原來是奇數(shù)，也有可能是原來的偶數(shù)分裂成兩個奇數(shù)循環(huán)。 * 推薦：（不錯的應(yīng)用） pku3590 The shuffle Problem // 把n 分解成若干個數(shù)，使得他們的lcm 最大。在所取的數(shù)都是素數(shù)冪的時候是最大的，所以可以用遞歸來枚舉所有的分解情況，而且由于要輸出序最小的，所以對于剩下的數(shù)可以直接單獨(dú)都作為一個循環(huán)，這樣就可以使得序最小了。此外，這道題目需要注意求最大的lcm 的時候不能用dp 來做，因?yàn)檫@個具有后效 性，局部最優(yōu)不一定使得全局最優(yōu)。 3. 素數(shù)，整數(shù)分解，歐拉函數(shù) 素數(shù)是可能數(shù)論里最永恒，最經(jīng)典的問題了（我們的隊(duì)名就叫PrimeMusic^^ ）。素數(shù)的判斷，篩法求素數(shù)，大素數(shù)的判斷 還有很多其他問題都會用到素數(shù)。 * 最水最水的：（心情不爽時用來解悶吧） pku1365 Prime Land pku2034 Antiprime Sequences// 直接搜索，用DL 優(yōu)化會快很多。 pku2739 Sum of Consecutive Prime Numbers pku3518 Prime Gap pku3126 Prime Path pku1595 Prime Cuts pku3641 Pseudoprime numbers pku2191 Mersenne Composite Numbers pku1730 Perfect Pth Powers pku2262 Goldbach39。s Conjecture pku2909 Goldbach39。s Conjecture * 篩法： pku2689 Prime Distance （很好的一個應(yīng)用）// 先找出sqrt(2^32) 內(nèi)的所有素數(shù)，然后類似篩選法篩選掉[l,u] 范圍內(nèi)的數(shù) * 反素數(shù)： zoj2562 More Divisors //waing... 后記：素數(shù)表少打了一個19 ～暈死啊～。 * 素數(shù)判斷，整數(shù)分解： 這兩題都要用到miller_rabin 的素數(shù)判斷和pollard_rho 的整數(shù)分解，算法書上都會有，應(yīng)該是屬于模板題吧，不過最好看懂自己敲一 遍。 pku1811 Prime Test // 學(xué)習(xí)miller 和pollard 的題目。 pku2429 GCD amp。 LCM Inverse // 分解lcm/gcd 為互質(zhì)的p,q ，要用到Miller Rabin 和Pollard rho 算法，基本上做出來之后都是模板題了。 * 歐拉函數(shù)： 數(shù)論里很多地方都能用到歐拉函數(shù)，很重要的。 pku1284 Primitive Roots （很水）// 定理：對于奇素數(shù)m, 原根個數(shù)為phi(phi(m)), 由于phi(m)=m1, 所以為phi(m1) pku2407 Relatives （很水） pku2773 Happy 2006 //n 之后的互質(zhì)的數(shù)都是n 之前的加上n 的倍數(shù)的。 pku2478 Farey Sequence （快速求歐拉函數(shù)）// 求前n 個歐拉函數(shù)的和，用學(xué)習(xí)指導(dǎo)里面的n*(1+lnln(n)) 的算法就可以了，非?？?。 pku3090 Visible Lattice Points （法雷級數(shù)） * 推薦：（歐拉函數(shù)，費(fèi)馬小定理） pku3358 Period of an Infinite Binary Expansion// 轉(zhuǎn)化為高次同余方程。 * 整數(shù)分解 這個也很重要的耶，包括大數(shù)的表示方法。 pku2992 Divisors// 注意預(yù)處理，有很多組數(shù)據(jù). ? fzu1753 Another Easy Problem// 記得n! 有多少個p 的冪是怎么求的。 hit2813 Garden visiting ? pku3101 Astronomy （分?jǐn)?shù)的最小公倍數(shù)）// 高精度gcd ，超時中。 4. 擴(kuò)展歐幾里得，線性同余，中國剩余定理 這應(yīng)該是數(shù)論里比較重要的一個部分吧，這類的題目也挺多，具體的內(nèi)容最好先看看數(shù)論書，我也整理過一些，可以參考參考： * 簡單題： pku1006 Biorhythms // 注意最后結(jié)果為0 或負(fù)數(shù)的情況 pku1061 青蛙的約會 pku2891 Strange Way to Express Integers //x==a1(mod m1),x==a2(mod m2), 兩個方程可以求出x ，然后重新令a1 為求出的解x,m1=lcm(m1,m2) ，然后繼續(xù)和后面的進(jìn)行求解。注意數(shù)據(jù)運(yùn)算過程中可能溢出的問題。 pku2115 C Looooops pku2142 The Balance // 枚舉，x=x0+b/d*t ，直到xmin(x+y) * 強(qiáng)烈推薦： sgu106 The equation // 求ax+by=c 的時候，考慮a,b 為零的特殊情況，此外，若a,b 不是非負(fù)數(shù)，那么擴(kuò)展歐幾里德會有問題，于是我們可以把求x,y 變?yōu)榍?x39。=x,y39。=y ，此時a,b, 就可以變?yōu)榉秦?fù)數(shù)來處理，同時x39。,y39。 的范圍也要相應(yīng)取反。而且在取得區(qū)間時候，要注意區(qū)間邊緣要進(jìn)行相應(yīng)的取 整。后記：要用cin,cout 才能AC ，用printf 會wa 。極度無奈中，偶然才發(fā)現(xiàn)的～_ ～! pku3708 Recurrent Function （經(jīng)典）// 具體數(shù)學(xué)第一章。對于每一位求出循環(huán)節(jié)m1 ，還有該位從m 達(dá)到k 最少要經(jīng)過r1 次標(biāo)號變化，于是就可以得到x==r1 (mod m1) ，然后同樣的方法求其他的位，接著就可以兩兩方程這樣解中國剩余定理。 5. 約瑟夫環(huán)問題 這個問題還是比較有意思的，不是很難。 * 簡單題： pku3517 And Then There Was One pku1781 In Danger pku1012 Joseph // 考慮剩下k+1 個人，那么上一個出局的人肯定是壞人，所以考慮接下來一定要最后一個壞人出局，所以m==0 或1(mod k+1) 。然后枚舉m ，再驗(yàn)證。 pku2244 Eeny Meeny Moo * 推薦： pku2886 Who Gets the Most Candies?// 線段樹+ 反素數(shù)。 6. 高斯消元法解方程 其實(shí)解方程并不是很難，就是按線性代數(shù)中學(xué)的那種方法，把系數(shù)矩陣化成上三角矩陣或數(shù)量矩陣，不過有些題目要判斷是否有解，或枚舉所有解。不過這類題目我認(rèn)為比較難的還是怎么去建立這個方程組，這個理解了，就沒什么大問題了。 * 簡單題： pku1222 EXTENDED LIGHTS OUT // 解異或運(yùn)算的方程。n*m 個方程和未知數(shù)。 pku1681 Painter39。s Problem pku1830 開關(guān)問題 // 以上三題做法都一樣。 * 推薦：