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