【正文】 Problem 題是說：給兩個(gè)互質(zhì)的數(shù)，要求出兩個(gè)數(shù)所不能組合出的正整數(shù)。在較大數(shù)的每一個(gè)等價(jià)類中找出最小的一數(shù)，它是較小數(shù)的倍數(shù)，那么在這個(gè)等價(jià)類中小于這個(gè)數(shù)的都是不能被表示出來的。最大的一個(gè)不能被表示出來的數(shù)是(n1)*mn 其中nm,由于n有n個(gè)等價(jià)類，一個(gè)類包含不可表示出的數(shù)是m1,總是是(n1)*(m1)/2 pku 2888 Magic Bracelet(帶約束的著色問題) 這題還是要用到波利亞定理，唯一的不同是計(jì)算矩陣的冪模，再求矩陣的跡。具體的推導(dǎo)就不知道是怎么來的。關(guān)于矩陣是指允許相鄰的兩種顏色之間有邊，這就形成了個(gè)無向圖。矩陣的n冪模，和快速冪乘的原理是一樣的。 pku 2917 Diophantus of Alexandria(不定方程，因數(shù)分解) 模擬下后發(fā)現(xiàn)，滿足1/x+1/y=1/z的x，y是z的約數(shù)，并且x，y互素。統(tǒng)計(jì)x，y的對(duì)數(shù)再加1（x=z,y=z是特殊的一對(duì)）。 后來看到討論里有公式，(xz)(yz)=z^2,計(jì)算小于z，并是z^2的約數(shù)就是答案了。 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ù)。 pku 3370 Halloween treats(鴿巢原理) 給定m個(gè)整數(shù)a1,a2,a3,..,am,存在整數(shù)k和l，0=kl=m,使得ak+1 + ak+2 + ... +al能夠被m整除。也就是說存在連續(xù)的一段al,...am,之和被m整除。考慮從a1...ai的和si，必定有si%m==0 或 si = sj (mod m),這種情況下取ai+1...aj,這段之和會(huì)是m的倍數(shù)。 pku 3128 Leonardo39。s Notebook(置換) 題目意思是：一個(gè)置換是否可以由另一個(gè)置換的平方得來的。一個(gè)置換的平方，原來偶數(shù)長的循環(huán)會(huì)被分裂成兩段長度相等的循環(huán)，而奇數(shù)長的循環(huán)不會(huì)被分裂。題目只是問是否存在，所以只要看所給置換中偶數(shù)長的循環(huán)是否成對(duì)，否則就不能由一個(gè)置換的平方得來。 pku 3244 Difference between Triplets(公式變形) 很巧妙的公式變形，可惜不自己想出來的。首先計(jì)算max(a,b,c)min(a,b,c)=(|ab|+|bc|+|ac|)/2,有了這個(gè)公式就可以把比較變成加。那么 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。 =(|WaWb|+|UaUb|+|HaHb|) 將讀入的數(shù)據(jù)轉(zhuǎn)化W,U，H三個(gè)數(shù)組，分別計(jì)算這三個(gè)數(shù)組任意兩個(gè)元素的差的絕對(duì)值之和。這里要用小于O(n^2)的算法，把數(shù)組排序后可以拿掉絕對(duì)值，統(tǒng)計(jì)每個(gè)元素作為減數(shù)出現(xiàn)的次數(shù)。 pku 3324 LucasLehmer Test(模運(yùn)算) 首先要用到高精度，用java很方便。在計(jì)算模的時(shí)候，由于是mod 2^p1,可以用移位來加速。 a=r (mod 2^p1) = a=k*(2^p1)+r,先算個(gè)打概的k,得到的r2^p1,繼續(xù)減2^p1。這樣比直接模運(yùn)算要快。 pku 3372 Candy Distribution(二次剩余系) 根據(jù)題目的意思可以得到方程 1+n(n+1)/2 =a (mod N),顯然這是一個(gè)二次模方程。要看N的二次完全剩余系是否都有解。 結(jié)論是N要是2^x,x=0,結(jié)論的證明還不知道。 pku 3516 Hide That Number（高精度） 題目是說給出一個(gè)數(shù)y，找到 x*11= y (mod 10^length(y)),如果y很小，直接求出逆來就能得到答案了，可是y很大，構(gòu)造的方法沒有想到，最后還是暴力做的。每次在y的前面加個(gè)數(shù)學(xué)(1,2..9),或是加上10這兩個(gè)數(shù)字，看新得到的數(shù)字是11的倍數(shù)。若是，就可以得到答案了。由于y很大，普通的高精度會(huì)超時(shí)，要增加進(jìn)制。 pku 3847 The Stable Marriage Problem（穩(wěn)定婚姻） 穩(wěn)定婚姻問題。用到了延遲認(rèn)可算法。用最優(yōu)方提出匹配，而被匹配者，不會(huì)立即接受，而是在提出要求者的集合中去掉，比當(dāng)前著差的元素，知道沒有人提出匹配，被匹配者才確定下匹配關(guān)系。值得一提的是，穩(wěn)定婚姻的存在性不能被保證。 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串。 下面是個(gè)模擬小數(shù)部分按二進(jìn)制表示，可以發(fā)現(xiàn)二進(jìn)制傳一定會(huì)有循環(huán)，因?yàn)閜=p%q,既然是循環(huán)，又是模運(yùn)行，這和p模q的階有關(guān)，p%q的階一定是q的歐拉函數(shù)的因子。這樣轉(zhuǎn)換成一個(gè)模方程:p*2^n = x(mod q),當(dāng)然p和q要互素，2和q互素。在計(jì)算前把q中的2去掉，p，q同除最大公因數(shù)。然后從1開始枚舉，所以的歐拉數(shù)的因子。 include define pr printf int main() { int i,p,q。 while(scanf(%d%d,amp。p,amp。q)==2){ pr(0.)。 for(i=1。i=100。i++) { p*=2。 pr(%d,p/q)。 p=p%q。 } pr(\n)。 } } /* 5 192 1010101010101010101010 */ pku 3590 The shuffle Problem(置換，數(shù)的分解) 題目求一個(gè)排列通過置換之后再回到原來的那個(gè)排列，對(duì)于給定的排列求出一個(gè)滿足置換次數(shù)最多的一個(gè)置換。一個(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ù)最大。要保證lcd最大應(yīng)該分解出來的每個(gè)數(shù)兩兩互素。由于數(shù)比較小，23是能最大的素?cái)?shù)，所以直接枚舉可以滿足。 pku 3641 Pseudoprime numbers(費(fèi)馬定理，快速冪乘) 簡單題，先看p是否是素?cái)?shù)，若是直接輸出no。否則計(jì)算(a^p)%p,若結(jié)果是a輸出yes，否則輸出no。 2008哈爾濱賽區(qū)網(wǎng)絡(luò)預(yù)選1007 The Luckiest number（歐拉定理運(yùn)用） 題目說要找個(gè)數(shù)t，它的數(shù)字全是8，對(duì)于給定的n，t要是n的整數(shù)倍，求最小的t。 賽后才發(fā)現(xiàn)這題并不拿，可能是我太菜了。這題問題可以轉(zhuǎn)換成8*(10^x1)/9 = 0 (mod n ),這樣就可以看出還有因子5和16的n是沒有解的。并且n是偶數(shù)時(shí)，其解是n除去2因子的解。最后就是求解 10^x = 1 (mod 9*n) n是一個(gè)奇數(shù)，所以(10,n)=1,這樣就可以根據(jù)歐拉定理 ,滿足等式的解只能是 euler(9*n)的因子。枚舉歐拉數(shù)的因子，最小的那個(gè)就是要求的解。由于n可以到2000000000，快速冪乘要支持64位運(yùn)算。 2008 成都網(wǎng)絡(luò)預(yù)選 1005 Farey Sequence Again(Farey Sequence ,構(gòu)造) 與其說是數(shù)學(xué)題，還不如說是個(gè)模擬題。Farey Sequence序列規(guī)律性很強(qiáng)，暴力模擬后發(fā)現(xiàn)有很多規(guī)律。要用到的一個(gè)性質(zhì)是 Fn中連續(xù)的3個(gè)元素，a1/b1 ,a2/b2,a3/b3。若a1+a3n 并且 b1+b3=n ,則 a2=a1+a3,b2=b1+b3。這個(gè)性質(zhì)很有用，根據(jù)它可以推出序列中前n項(xiàng)的分子不超過3，而且在構(gòu)造的時(shí)候也要用到這個(gè)性質(zhì)，找個(gè)第一個(gè)分母是2和3的元素的位置，都可以通過觀察看出規(guī)律。序列就分成了3段，第一段分子只有1，第二段分子有1和2，而且是2，1，2，1，2。這樣循環(huán)的。第三段有1，2，3，也會(huì)出現(xiàn)循環(huán)，或是3，1，3，2 或是3，2，3，1這樣的循環(huán)結(jié)。所以的規(guī)律都可以在模擬的序列中看出。只有3為分子時(shí)看不出規(guī)律，但是這樣的元素左右兩個(gè)一定是分子為1和2的兩個(gè)元素，根據(jù)性質(zhì)，知道3周圍的兩個(gè)元素的分母，就可以得出分子為3的元素的分母 2008 哈爾濱現(xiàn)場賽 Simple Addition Expression hdu2451 通過讀題發(fā)現(xiàn)滿足要求的數(shù)字，最高位由1，2，3組成，最低位由0，1，2組成，中間由0，1，2，3組成。計(jì)算小于n的數(shù)有多少個(gè)這種數(shù)就是答案。 2008 哈爾濱現(xiàn)場賽 Kdimension number hdu2447 讀題后發(fā)現(xiàn)K要么是p,要么是p^2 (p為素?cái)?shù))，且p=97,K維數(shù)n的情況只有三種。 一，當(dāng)k為p時(shí)，n=(p39。)^(p1) 二，當(dāng)k為p^2時(shí)，n=(p139。)^(p1)*(p239。)^(p1)或n=(p139。)^(p^21) 三，當(dāng)k為1是，n=1。 zoj 2562 More Divisors(反素?cái)?shù)，dp) 反素?cái)?shù)是指在不大于n數(shù)中含有最多約數(shù)，值最小的一個(gè)，比如2，4，6。都是反素?cái)?shù)。題目要求在小于10^16中的反素?cái)?shù)。 由于反素?cái)?shù)要求約數(shù)盡量多，所以素因子個(gè)數(shù)要盡量少，而指數(shù)要盡量大，這樣一個(gè)數(shù)成為反素?cái)?shù)的機(jī)會(huì)就大。所以只要考慮前13個(gè)素?cái)?shù)所能組成的數(shù)就可以。轉(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ù)的最小值。p(i)表示第i個(gè)素?cái)?shù),j%(k+1)==0 要注意的地方: j不超過50000。