【正文】 pku2480 Longge39。另外在pku3695 上同樣的題目由于時(shí)限很緊，所以可以對(duì)坐標(biāo)進(jìn)行離散化。 * 鴿巢原理： pku2356 Find a multiple // 同下。 * 簡(jiǎn)單： pku3070 Fibonacci pku3233 Matrix Power Series pku3735 Training little cats 8. 高次同余方程 有關(guān)這個(gè)問(wèn)題我應(yīng)該是沒(méi)什么發(fā)言權(quán)了，A^B%C=D ，我現(xiàn)在只會(huì)求D 和B ，唉，很想知道A 該怎么求。 pku2065 SETI// 與上題一樣。 6. 高斯消元法解方程 其實(shí)解方程并不是很難，就是按線性代數(shù)中學(xué)的那種方法，把系數(shù)矩陣化成上三角矩陣或數(shù)量矩陣，不過(guò)有些題目要判斷是否有解，或枚舉所有解。而且在取得區(qū)間時(shí)候，要注意區(qū)間邊緣要進(jìn)行相應(yīng)的取 整。 hit2813 Garden visiting ? pku3101 Astronomy （分?jǐn)?shù)的最小公倍數(shù)）// 高精度gcd ，超時(shí)中。 pku2429 GCD amp。題目只是問(wèn)是否存在，所以只要看所給置換中偶數(shù)長(zhǎng)的循環(huán)是否成對(duì)，否則就不能由一個(gè)置換的平方得來(lái)。 * 簡(jiǎn)單題：（應(yīng)該理解概念就可以了） pku3270 Cow Sorting // 列出置換，然后對(duì)于每一個(gè)置換循環(huán)，不斷用環(huán)中的最小的那個(gè)和其他的進(jìn)行換位，可以得到最優(yōu)。 簡(jiǎn)單： ural1057 Amount of degrees spoj1182 Sorted bit squence hdu3271 SNIBB 較難： spoj2319 Sequence sgu390 Tickets 對(duì)數(shù)學(xué)類(lèi)題目小結(jié)中的題目的簡(jiǎn)單解題報(bào)告： /******************************************************************************************/ 定理，polya 計(jì)數(shù)法 這個(gè)大家可以看brudildi 的《組合數(shù)學(xué)》，那本書(shū)的這一章寫(xiě)的很詳細(xì)也很容易理解。就先推薦幾道題目吧，這里涉及到了一個(gè)babystep，giantstep算法。 pku1284 Primitive Roots （很水） pku2407 Relatives （很水） pku2773 Happy 2006 pku2478 Farey Sequence （快速求歐拉函數(shù)） pku3090 Visible Lattice Points （法雷級(jí)數(shù)） *推薦：（歐拉函數(shù)，費(fèi)馬小定理） pku3358 Period of an Infinite Binary Expansion *整數(shù)分解 這個(gè)也很重要的耶，包括大數(shù)的表示方法。 *簡(jiǎn)單題：（應(yīng)該理解概念就可以了） pku3270 Cow Sorting pku1026 Cipher *置換冪運(yùn)算： pku1721 CARDS pku3128 Leonardo39。s Conjecture *篩法： pku2689 Prime Distance（很好的一個(gè)應(yīng)用） *反素?cái)?shù)： zoj2562 More Divisors *素?cái)?shù)判斷，整數(shù)分解： 這兩題都要用到miller_rabin的素?cái)?shù)判斷和pollard_rho的整數(shù)分解，算法書(shū)上都會(huì)有，應(yīng)該是屬于模板題吧，不過(guò)最好看懂自己敲一遍。s Problem pku1830 開(kāi)關(guān)問(wèn)題 *推薦： pku2947 Widget Factory pku2065 SETI *強(qiáng)烈推薦： pku1753 Flip Game pku3185 The Water Bowls *變態(tài)題： pku1487 SinglePlayer Games 用矩陣來(lái)解決問(wèn)題確實(shí)很常見(jiàn)，但我現(xiàn)在用到還不是很好，很多難題我還不會(huì)做。s problem pku1792 Hexagonal Routes ，區(qū)間計(jì)數(shù)，計(jì)數(shù)序列 這些題目可能需要一些組合數(shù)學(xué)知識(shí)，基本上高中的知識(shí)就夠了。 *簡(jiǎn)單： pku3273 Monthly Expense pku3258 River Hopscotch pku1905 Expanding Rods pku3122 Pie *推薦： pku1845 Sumdiv 無(wú)意中接觸到這個(gè)算法，還蠻有意思的，《組合數(shù)學(xué)》中有詳細(xì)的介紹。其中矩陣的冪可以預(yù)先求出所有matrix[2^i] 出來(lái)，然后根據(jù)二進(jìn)制來(lái) 求。 pku3128 Leonardo39。 3. 素?cái)?shù)，整數(shù)分解，歐拉函數(shù) 素?cái)?shù)是可能數(shù)論里最永恒，最經(jīng)典的問(wèn)題了（我們的隊(duì)名就叫PrimeMusic^^ ）。s Conjecture * 篩法： pku2689 Prime Distance （很好的一個(gè)應(yīng)用）// 先找出sqrt(2^32) 內(nèi)的所有素?cái)?shù)，然后類(lèi)似篩選法篩選掉[l,u] 范圍內(nèi)的數(shù) * 反素?cái)?shù)： zoj2562 More Divisors //waing... 后記：素?cái)?shù)表少打了一個(gè)19 ～暈死啊～。 pku3090 Visible Lattice Points （法雷級(jí)數(shù)） * 推薦：（歐拉函數(shù)，費(fèi)馬小定理） pku3358 Period of an Infinite Binary Expansion// 轉(zhuǎn)化為高次同余方程。=y ，此時(shí)a,b, 就可以變?yōu)榉秦?fù)數(shù)來(lái)處理，同時(shí)x39。 * 簡(jiǎn)單題： pku3517 And Then There Was One pku1781 In Danger pku1012 Joseph // 考慮剩下k+1 個(gè)人，那么上一個(gè)出局的人肯定是壞人，所以考慮接下來(lái)一定要最后一個(gè)壞人出局，所以m==0 或1(mod k+1) 。s Problem pku1830 開(kāi)關(guān)問(wèn)題 // 以上三題做法都一樣。 // 同類(lèi)題目，我自己加上去的。另外進(jìn)行最后答案輸出的時(shí)候，vector 的size （）是返回unsigned int 的，如果size( ）是0 ，那么size()1 就是2^321 了，所以這里就需要特別注意。假設(shè)bd, （此處b,d 已除k ）那么對(duì)于=b, 直接用歐拉函數(shù)就可以了，對(duì)于[b+1,d] 之 間的數(shù)，對(duì)于每一個(gè)分解質(zhì)因數(shù)，然后利用容斥原理，求出［1,b ］之間和這個(gè)數(shù)互質(zhì)的個(gè)數(shù)。其實(shí)可以進(jìn)行分析的。區(qū)間計(jì)數(shù)問(wèn)題一般不難，但寫(xiě)的時(shí)候需要仔細(xì)一些，各種情況要考慮到位。 f(x^t)=1+x+x^2+..+x^t=(1x^(t+1))/(1x)。 樹(shù)狀數(shù)組 hdu 3333 先求出每個(gè)位置后面和它一樣的最近的那個(gè)數(shù)的位置next[i] ，然后用樹(shù)狀數(shù)組記錄不重復(fù)的前n 個(gè)數(shù)的和，接著對(duì)詢(xún) 問(wèn)區(qū)間排序，從左到右做，記left 為在當(dāng)前區(qū)間左邊的那些數(shù)，通過(guò)樹(shù)狀數(shù)組，將left 到next[left]1 之間的所有的數(shù)都減去 val[left] ，然后就可以直接像sum[i]sum[j] 那樣方便的求出區(qū)間里面沒(méi)有重復(fù)的數(shù)的和。如果每次重復(fù)的數(shù)，輸出c[n][m]就可以。這樣搜索的空間就只有n的剩余系了?？紤]一個(gè)完整的聯(lián)通圖，可以標(biāo)記兩個(gè)點(diǎn)1，2。題目還要求mod 9901,這雖然是個(gè)素?cái)?shù)，但是數(shù)據(jù)中出現(xiàn)了p1 = 0 (mod 9901)的情況，這時(shí)f(p^t)=t+1 (mod 9901),要特殊處理下，其余用快速冪乘。 為了找S的一組解，可以把S變小，來(lái)得到S的解。 pku 2142 The Balance(不定方程) 不定方程題，解a*x+b*y=d 。t。 for(i=0。itmp。先求出任意兩個(gè)數(shù)的差(要正的),找個(gè)最小的數(shù)，使其不是前面求的差的約數(shù)。在較大數(shù)的每一個(gè)等價(jià)類(lèi)中找出最小的一數(shù)，它是較小數(shù)的倍數(shù)，那么在這個(gè)等價(jià)類(lèi)中小于這個(gè)數(shù)的都是不能被表示出來(lái)的。 pku2992 Divisors (組合數(shù)，因子個(gè)數(shù)) 計(jì)算C(n,k)的因子個(gè)數(shù),由于n很小，最大為431，所以可以把1～431的所有數(shù)先因式分解，再來(lái)統(tǒng)計(jì)n*(n1)...(nk+1)/k*(k1)...1的素因子個(gè)數(shù)。 pku 3244 Difference between Triplets(公式變形) 很巧妙的公式變形，可惜不自己想出來(lái)的。這樣比直接模運(yùn)算要快。 pku 3847 The Stable Marriage Problem（穩(wěn)定婚姻） 穩(wěn)定婚姻問(wèn)題。然后從1開(kāi)始枚舉，所以的歐拉數(shù)的因子。 pr(%d,p/q)。否則計(jì)算(a^p)%p,若結(jié)果是a輸出yes，否則輸出no。 2008 成都網(wǎng)絡(luò)預(yù)選 1005 Farey Sequence Again(Farey Sequence ,構(gòu)造) 與其說(shuō)是數(shù)學(xué)題，還不如說(shuō)是個(gè)模擬題。所以的規(guī)律都可以在模擬的序列中看出。)^(p^21) 三，當(dāng)k為1是，n=1。 。都是反素?cái)?shù)。計(jì)算小于n的數(shù)有多少個(gè)這種數(shù)就是答案。要用到的一個(gè)性質(zhì)是 Fn中連續(xù)的3個(gè)元素，a1/b1 ,a2/b2,a3/b3。 賽后才發(fā)現(xiàn)這題并不拿，可能是我太菜