【正文】 位從m 達到k 最少要經(jīng)過r1 次標(biāo)號變化，于是就可以得到x==r1 (mod m1) ，然后同樣的方法求其他的位，接著就可以兩兩方程這樣解中國剩余定理。n*m 個方程和未知數(shù)。 pku3185 The Water Bowls // 同樣如果對于無數(shù)解的時候，就需要對解進行枚舉。 pku2417 Discrete Logging //hash ，最直接的離散對數(shù) ？ hdu2815 Mod Tree // 超時中，時限好像挺緊的。 * 容斥原理： hdu1695 GCD // 求gcd(x,y)=k 的個數(shù)，相當(dāng)于求gcd(x/k,y/k)=1 的個數(shù)，其中x/k 在[a/k,b/k],y/k 在[c/k,d/k] 之間。我很多都是在參考別人思路的情況下做的，能自己想出來真的很不容易。 d*[gcd(i,n)==d]), 枚舉所有n 的約數(shù)d ，然后對于n/d ，找出所有和n/d 互質(zhì)的數(shù)的個數(shù)就是gcd(i,n)==d 的個數(shù)，從而用歐拉 函數(shù)解決。s? * 推薦： pku3252 Round Numbers * 計數(shù)序列： pku1430 Binary Stirling Numbers pku2515 Birthday Cake pku1707 Sum of powers 12. 二分法 二分的思想還是很重要的，這里就簡單推薦幾個純粹的二分題。 簡單： ural1057 Amount of degrees spoj1182 Sorted bit squence hdu3271 SNIBB 較難： spoj2319 Sequence sgu390 Tickets 歐拉函數(shù)。枚舉前一半的未知數(shù)可以到達的值(用hash表保存)，再枚舉后一半，這樣可以加快枚舉。s in binary representations of results of respective expressions: then mimic a bitwise AND operation by intersecting these two sets: to obtain the parity of a Stirling number of the second kind in O(1) time. pku 1465 Multiple(BFS,整除) 給幾個一些數(shù)學(xué)，找出由這些數(shù)字組成的數(shù)中最小的一個能整除n的數(shù)。還來在網(wǎng)上看到一種更好的解法。 pku 1845 Sumdiv(積性函數(shù)，因子和) 求a^b的因子和(包括1和a^b),由于因子和是積性函數(shù)。 pku 1831 不定方程組(構(gòu)造解) 這個題目很有意思，說a1+a2..an=s,1/a1+1/a2....+1/an=1。所以事先保留一些小的S的解。一般解為x=x0b39?？梢苑謩e計算f(b),f(a1)的大小,其中 ab f(n)表示1到n數(shù)字出現(xiàn)的統(tǒng)計。else start=1。 pku 2769 Reduced ID Numbers(同余) 給出n個數(shù)，找一個數(shù)p,使得沒個數(shù)mod p的值不相等。= c (mod lcm(b1,b2))表示。統(tǒng)計x，y的對數(shù)再加1（x=z,y=z是特殊的一對）。一個置換的平方，原來偶數(shù)長的循環(huán)會被分裂成兩段長度相等的循環(huán)，而奇數(shù)長的循環(huán)不會被分裂。在計算模的時候，由于是mod 2^p1,可以用移位來加速。若是，就可以得到答案了。這樣轉(zhuǎn)換成一個模方程:p*2^n = x(mod q),當(dāng)然p和q要互素，2和q互素。i=100。由于數(shù)比較小，23是能最大的素數(shù)，所以直接枚舉可以滿足。枚舉歐拉數(shù)的因子，最小的那個就是要求的解。這樣循環(huán)的。)^(p1)*(p239。轉(zhuǎn)移方程 f[i][j]= min{f[i1][j/(k+1)]*p(i)^k} f[i][j] 表示i個素數(shù)，有j個約數(shù)的最小值。 由于反素數(shù)要求約數(shù)盡量多，所以素因子個數(shù)要盡量少，而指數(shù)要盡量大，這樣一個數(shù)成為反素數(shù)的機會就大。 一，當(dāng)k為p時，n=(p39。這個性質(zhì)很有用，根據(jù)它可以推出序列中前n項的分子不超過3，而且在構(gòu)造的時候也要用到這個性質(zhì)，找個第一個分母是2和3的元素的位置，都可以通過觀察看出規(guī)律。并且n是偶數(shù)時，其解是n除去2因子的解。一個置換可以分解成多個循環(huán)，每次置換元素之和在同一個循環(huán)中的元素發(fā)生轉(zhuǎn)換，同一個循環(huán)中循環(huán)節(jié)是元素的個數(shù)，所以這個題是要把一個數(shù)分成多個數(shù)的和，讓這些數(shù)的最小公倍數(shù)最大。q)==2){ pr(0.)。 pku 3358 Period of an Infinite Binary Expansion(數(shù)論，歐拉定理) 這個題目是求兩個數(shù)相除p/q，結(jié)果的小數(shù)部分用二進制表示，當(dāng)q不是2的冪時，這個二進制是個無線循環(huán)的01串。 pku 3516 Hide That Number（高精度） 題目是說給出一個數(shù)y，找到 x*11= y (mod 10^length(y)),如果y很小，直接求出逆來就能得到答案了，可是y很大，構(gòu)造的方法沒有想到，最后還是暴力做的。這里要用小于O(n^2)的算法，把數(shù)組排序后可以拿掉絕對值，統(tǒng)計每個元素作為減數(shù)出現(xiàn)的次數(shù)。 pku 3128 Leonardo39。矩陣的n冪模，和快速冪乘的原理是一樣的。c=a1 (mod b1),c=a2 (mod b2) c=a1+b1*x, a1+b1*x= a2 (mod b2),用擴展歐幾里德求出c。 } pku 2429 gcd lcm Inverse 大數(shù)分解，要分解的數(shù)很大，到了2^63,普通的素數(shù)表方法行不通，要使用Pollard分解，分解lcm/gcd。 tmp=(a/times)%10。 pku 3352 In Danger(約瑟夫環(huán)) 簡單題，和具體數(shù)學(xué)第一章提到的問題是一樣的，講每數(shù)2去掉一人，求勝利人的編號。*x+b39。更重要的是當(dāng)S一定大時，一定會有解。那么只有統(tǒng)計出所有點的組合情況就可以得出答案了。將他們乘在一起就有了上面的式子。 pku 1737 Connected Graph(組合數(shù)學(xué)，高精度) 題目是求n個點用邊鏈接，形成聯(lián)通圖的方案總算。原文如下： Using a Sierpiński triangle, it39。結(jié)果就是 2^(dig[2]dig[5])*3^(dig[3])*7^(dig[7])*9^(dig[9]) mod 10 ，用快速冪乘來算。 pku3487 The Stable Marriage Problem zoj1576 Marriage is Stable 14. 數(shù)位類統(tǒng)計問題 在航點月賽中第一次接觸到這類問題，scau 大牛little 龍推薦我看了一篇論文，09 年劉聰?shù)摹稖\談數(shù)位類統(tǒng)計問題》，這篇論文相當(dāng)精彩，也相當(dāng)詳 細，每道題都有詳細的分析和作者的參考代碼。 都還挺有意思，可以去看看《組合數(shù)學(xué)》。s problem//sigma(gcd(i,n))=sigma(d|n amp。log1000 和 log40 還是有差別的。 pku3370 Halloween treats////n 個數(shù)，尋找c 個(c=n) ，使得他們的和為c 的倍數(shù)。就先推薦幾道題目吧，這里涉及到了一個baby step ，giantstep 算法。 * 強烈推薦： pku1753 Flip Game // 數(shù)據(jù)范圍比較小，枚舉可過。不過這類題目我認為比較難的還是怎么去建立這個方程組，這個理解了，就沒什么大問題了。后記：要用cin,cout 才能AC ，用printf 會wa 。 4. 擴展歐幾里得，線性同余，中國剩余定理 這應(yīng)該是數(shù)論里比較重要的一個部分吧，這類的題目也挺多，具體的內(nèi)容最好先看看數(shù)論書，我也整理過一些，可以參考參考： * 簡單題： pku1006 Biorhythms // 注意最后結(jié)果為0 或負數(shù)的情況 pku1061 青蛙的約會 pku2891 Strange Way to Express Integers //x==a1(mod m1),x==a2(mod m2), 兩個方程可以求出x ，然后重新令a1 為求出的解x,m1=lcm(m1,m2) ，然后繼續(xù)和后面的進行求解。 LCM Inverse // 分解lcm/gcd 為互質(zhì)的p,q ，要用到Miller Rabin 和Pollard rho 算法，基本上做出來之后都是模板題了。 還有很多其他問題都會用到素數(shù)。 補充：因為如果所給置換的循環(huán)是偶數(shù)，則肯定是由分裂過來的，那么一定是成對的，否則如果是奇數(shù)，那么有可能是原來是奇數(shù)，也有可能是原來的偶數(shù)分裂成兩個奇數(shù)循環(huán)。另外還有一種情況就是用整個置換最小的那個和該環(huán)進行換位，對于每個環(huán)求出這兩個的最小值加起來就可以了。最好能完全看懂了，理解了再去做題，不要只記個公式。 fzu1759 Super A^B mod C pku3243 Clever Y pku2417 Discrete Logging hdu2815 Mod Tree ，鴿巢原理 很有用的兩個定理，但好像單獨考這兩個定理的不是很多。 pku2992 Divisors fzu1753 Another Easy Problem hit2813 Garden v