【正文】 。轉(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ì)就大。都是反素?cái)?shù)。)^(p^21) 三，當(dāng)k為1是，n=1。)^(p1)*(p239。 一，當(dāng)k為p時(shí)，n=(p39。計(jì)算小于n的數(shù)有多少個(gè)這種數(shù)就是答案。所以的規(guī)律都可以在模擬的序列中看出。這樣循環(huán)的。這個(gè)性質(zhì)很有用，根據(jù)它可以推出序列中前n項(xiàng)的分子不超過3，而且在構(gòu)造的時(shí)候也要用到這個(gè)性質(zhì)，找個(gè)第一個(gè)分母是2和3的元素的位置，都可以通過觀察看出規(guī)律。要用到的一個(gè)性質(zhì)是 Fn中連續(xù)的3個(gè)元素，a1/b1 ,a2/b2,a3/b3。 2008 成都網(wǎng)絡(luò)預(yù)選 1005 Farey Sequence Again(Farey Sequence ,構(gòu)造) 與其說是數(shù)學(xué)題，還不如說是個(gè)模擬題。枚舉歐拉數(shù)的因子，最小的那個(gè)就是要求的解。并且n是偶數(shù)時(shí)，其解是n除去2因子的解。 賽后才發(fā)現(xiàn)這題并不拿，可能是我太菜了。否則計(jì)算(a^p)%p,若結(jié)果是a輸出yes，否則輸出no。由于數(shù)比較小，23是能最大的素?cái)?shù)，所以直接枚舉可以滿足。一個(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ù)最大。 } pr(\n)。 pr(%d,p/q)。i=100。q)==2){ pr(0.)。 while(scanf(%d%d,amp。然后從1開始枚舉，所以的歐拉數(shù)的因子。這樣轉(zhuǎn)換成一個(gè)模方程:p*2^n = x(mod q),當(dāng)然p和q要互素，2和q互素。 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è)無線循環(huán)的01串。用最優(yōu)方提出匹配，而被匹配者，不會(huì)立即接受，而是在提出要求者的集合中去掉，比當(dāng)前著差的元素，知道沒有人提出匹配，被匹配者才確定下匹配關(guān)系。 pku 3847 The Stable Marriage Problem（穩(wěn)定婚姻） 穩(wěn)定婚姻問題。若是，就可以得到答案了。 pku 3516 Hide That Number（高精度） 題目是說給出一個(gè)數(shù)y，找到 x*11= y (mod 10^length(y)),如果y很小，直接求出逆來就能得到答案了，可是y很大，構(gòu)造的方法沒有想到，最后還是暴力做的。要看N的二次完全剩余系是否都有解。這樣比直接模運(yùn)算要快。在計(jì)算模的時(shí)候，由于是mod 2^p1,可以用移位來加速。這里要用小于O(n^2)的算法，把數(shù)組排序后可以拿掉絕對(duì)值，統(tǒng)計(jì)每個(gè)元素作為減數(shù)出現(xiàn)的次數(shù)。那么 D(Ta, Tb) = max {Ia ? Ib, Ja ? Jb, Ka ? Kb} ? min {Ia ? Ib, Ja ? Jb, Ka ? Kb} =(|IaIbJa+Jb|+|JaJbKa+Kb|+|IaIbKa+Kb|)/2 令I(lǐng)aJa=Wa,JaKa=Ua,IaKa=Ha。 pku 3244 Difference between Triplets(公式變形) 很巧妙的公式變形，可惜不自己想出來的。一個(gè)置換的平方，原來偶數(shù)長的循環(huán)會(huì)被分裂成兩段長度相等的循環(huán)，而奇數(shù)長的循環(huán)不會(huì)被分裂。 pku 3128 Leonardo39。也就是說存在連續(xù)的一段al,...am,之和被m整除。 pku2992 Divisors (組合數(shù)，因子個(gè)數(shù)) 計(jì)算C(n,k)的因子個(gè)數(shù),由于n很小，最大為431，所以可以把1～431的所有數(shù)先因式分解，再來統(tǒng)計(jì)n*(n1)...(nk+1)/k*(k1)...1的素因子個(gè)數(shù)。統(tǒng)計(jì)x，y的對(duì)數(shù)再加1（x=z,y=z是特殊的一對(duì)）。矩陣的n冪模，和快速冪乘的原理是一樣的。具體的推導(dǎo)就不知道是怎么來的。在較大數(shù)的每一個(gè)等價(jià)類中找出最小的一數(shù)，它是較小數(shù)的倍數(shù)，那么在這個(gè)等價(jià)類中小于這個(gè)數(shù)的都是不能被表示出來的。= c (mod lcm(b1,b2))表示。c=a1 (mod b1),c=a2 (mod b2) c=a1+b1*x, a1+b1*x= a2 (mod b2),用擴(kuò)展歐幾里德求出c?？梢酝ㄟ^先求 兩個(gè)方程的解，這樣就將兩個(gè)方程和并成一個(gè)，直達(dá)只剩下一個(gè)為止就可以的到答案了。先求出任意兩個(gè)數(shù)的差(要正的),找個(gè)最小的數(shù)，使其不是前面求的差的約數(shù)。 pku 2769 Reduced ID Numbers(同余) 給出n個(gè)數(shù)，找一個(gè)數(shù)p,使得沒個(gè)數(shù)mod p的值不相等。 } pku 2429 gcd lcm Inverse 大數(shù)分解，要分解的數(shù)很大，到了2^63,普通的素?cái)?shù)表方法行不通，要使用Pollard分解，分解lcm/gcd。 aa[tmp]+=a%times+1。itmp。else start=1。 tmp=(a/times)%10。i++)aa[i]+=len*times。 for(i=0?？梢苑謩e計(jì)算f(b),f(a1)的大小,其中 ab f(n)表示1到n數(shù)字出現(xiàn)的統(tǒng)計(jì)。 pku 3352 In Danger(約瑟夫環(huán)) 簡單題，和具體數(shù)學(xué)第一章提到的問題是一樣的，講每數(shù)2去掉一人，求勝利人的編號(hào)。 pku 2154 Color(波利亞定理,著色問題) 一個(gè)經(jīng)典的著色問題，題目描述的是一個(gè)正常的旋轉(zhuǎn)群，它的輪換指標(biāo)為1/n*sigma(euler(d)*(xd)^(n/d)) ，其中d為n的所有因子。t。一般解為x=x0b39。*x+b39。a/=k,b/=k,d/=k。 pku 2142 The Balance(不定方程) 不定方程題，解a*x+b*y=d 。所以事先保留一些小的S的解。更重要的是當(dāng)S一定大時(shí)，一定會(huì)有解?；騪/2+1/3+1/6=1,p*2+9=S。 為了找S的一組解，可以把S變小，來得到S的解。 pku 1831 不定方程組(構(gòu)造解) 這個(gè)題目很有意思，說a1+a2..an=s,1/a1+1/a2....+1/an=1。那么只有統(tǒng)計(jì)出所有點(diǎn)的組合情況就可以得出答案了。這題不要去算具體的面積，答案和所選點(diǎn)的奇偶性有關(guān)，點(diǎn)的只有4種類型，(0,0),(1,1),(1,0),(0,1)。題目還要求mod 9901,這雖然是個(gè)素?cái)?shù)，但是數(shù)據(jù)中出現(xiàn)了p1 = 0 (mod 9901)的情況，這時(shí)f(p^t)=t+1 (mod 9901),要特殊處理下，其余用快速冪乘。 pku 1845 Sumdiv(積性函數(shù)，因子和) 求a^b的因子和(包括1和a^b),由于因子和是積性函數(shù)。將他們乘在一起就有了上面的式子。在g1中最少要有一個(gè)點(diǎn)與g2中的點(diǎn)2鏈接?？紤]一個(gè)完整的聯(lián)通圖，可以標(biāo)記兩個(gè)點(diǎn)1，2。還來在網(wǎng)上看到一種更好的解法。 pku 1737 Connected Graph(組合數(shù)學(xué)，高精度) 題目是求n個(gè)點(diǎn)用邊鏈接，形成聯(lián)通圖的方案總算。從最高位開始，一位一位確定dfs下去，每次都要保證已確定的位的所有組合不少于題目給出的序號(hào)。這樣搜索的空間就只有n的剩余系了。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ù)。原文如下： Using a Sierpiński triangle, it39。注意幾個(gè)邊界條件，c[0][0]=1,z[1][0...a[1]]=1,z[i][1]=i 2=i=s。如果每次重復(fù)的數(shù)，輸出c[n][m]就可以。枚舉前一半的未知數(shù)可以到達(dá)的值(用hash表保存)，再枚舉后一半，這樣可以加快枚舉。結(jié)果就是 2^(dig[2]dig[5])*3^(dig[3])*7^(dig[7])*9^(dig[9]) mod 10 ，用快速冪乘來算。只有各位上的數(shù)字才會(huì)影響最后一個(gè)非零數(shù)字。 樹狀數(shù)組 hdu 3333 先求出每個(gè)位置后面和它一樣的最近的那個(gè)數(shù)的位置next[i] ，然后用樹狀數(shù)組記錄不重復(fù)的前n 個(gè)數(shù)的和，接著對(duì)詢 問區(qū)間排序，從左到右做，記left 為在當(dāng)前區(qū)間左邊的那些數(shù)，通過樹狀數(shù)組，將left 到next[left]1 之間的所有的數(shù)都減去 val[left] ，然后就可以直接像sum[i]sum[j] 那樣方便的求出區(qū)間里面沒有重復(fù)的數(shù)的和。 簡單： ural1057 Amount of degrees spoj1182 Sorted bit squence hdu3271 SNIBB 較難： spoj2319 Sequence sgu390 Tickets 歐拉函數(shù)。 pku3487 The Stable Marriage Problem zoj1576 Marriage is Stable 14. 數(shù)位類統(tǒng)計(jì)問題 在航點(diǎn)月賽中第一次接觸到這類問題，scau 大牛little 龍推薦我看了一篇論文，09 年劉聰?shù)摹稖\談數(shù)位類統(tǒng)