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