天天看點
傳回

數學專題（會把題解一一補上）

  1. 從放暑假前周sir給我講了一個用polya計數法和burnside定理做的題目（pku2409）後，突然覺得組合數學挺有意思，然後從那時起到現在幾乎都在做這類的題目。
  2. 做到現在感覺這類題目的一些基本知識點都差不多有所了解了，水題也刷了不少，但還有很多難題自己實在是做不動，是以準備把這類題目先放一放，然後把前段時間做的水題整理一下（供以後的初學者參考，大牛就不要看了哈，都是水題）。剩下的比較難的題目就慢慢來吧，以後做出來再不上，這個小結會不斷地更新。也希望大家有好的題目可以推薦一下，分享一下哈。
  • 感謝：周sir，J_factory和福州大學神牛aekdycoin，大連理工大學神牛czyuan。
  • 不扯了，進入主題：
  • 1.burnside定理，polya計數法
  • 這個專題我單獨寫了個小結，大家可以簡單參考一下：polya 計數法，burnside定理小結
  • 2.置換，置換的運算
  • 置換的概念還是比較好了解的，《組合數學》裡面有講。對于置換的幂運算大家可以參考一下潘震皓的那篇《置換群快速幂運算研究與探讨》，寫的很好。
  • *簡單題：（應該了解概念就可以了）
  • pku3270 Cow Sorting
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=3270​​
  • pku1026 Cipher
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=1026​​
  • *置換幂運算：
  • pku1721 CARDS
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1721​​
  • pku3128 Leonardo's Notebook
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3128​​
  • *推薦：（不錯的應用）
  • pku3590 The shuffle Problem
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3590​​
  • 3.素數，整數分解，歐拉函數
  • 素數是可能數論裡最永恒，最經典的問題了（我們的隊名就叫PrimeMusic^-^）。素數的判斷，篩法求素數，大素數的判斷···還有很多其他問題都會用到素數。
  • *最水最水的：（心情不爽時用來解悶吧）
  • pku1365 Prime Land
  • pku2034 Anti-prime Sequences
  • pku2739 Sum of Consecutive Prime Numbers
  • pku3518 Prime Gap
  • pku3126 Prime Path
  • pku1595 Prime Cuts
  • pku3641 Pseudoprime numbers
  • pku2191 Mersenne Composite Numbers
  • pku1730 Perfect Pth Powers
  • pku2262 Goldbach's Conjecture
  • pku2909 Goldbach's Conjecture
  • *篩法：
  • pku2689 Prime Distance（很好的一個應用）
  • ​​http://162.105.81.212/JudgeOnline/problem?id=2689​​
  • *反素數：
  • zoj2562 More Divisors
  • ​​http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2562​​
  • *素數判斷，整數分解：
  • 這兩題都要用到miller_rabin的素數判斷和pollard_rho的整數分解，算法書上都會有，應該是屬于模闆題吧，不過最好看懂自己敲一遍。
  • pku1811 Prime Test
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=1811​​
  • pku2429 GCD & LCM Inverse
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=2429​​
  • *歐拉函數：
  • 數論裡很多地方都能用到歐拉函數，很重要的。
  • pku1284 Primitive Roots （很水）
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=1284​​
  • pku2407 Relatives （很水）
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=2407​​
  • pku2773 Happy 2006
  • ​​http://162.105.81.212/JudgeOnline/problem?id=2773​​
  • pku2478 Farey Sequence （快速求歐拉函數）
  • ​​http://162.105.81.212/JudgeOnline/problem?id=2478​​
  • pku3090 Visible Lattice Points （法雷級數）
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=3090​​
  • *推薦：（歐拉函數，費馬小定理）
  • pku3358 Period of an Infinite Binary Expansion
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=3358​​
  • *整數分解
  • 這個也很重要的耶，包括大數的表示方法。
  • pku2992 Divisors
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=2992​​
  • fzu1753 Another Easy Problem
  • ​​http://acm.fzu.edu.cn/problem.php?pid=1753​​
  • hit2813 Garden visiting
  • ​​http://acm-hit.sunner.cn/judge/show.php?Proid=2813​​
  • pku3101 Astronomy （分數的最小公倍數）
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=3101​​
  • 4.擴充歐幾裡得，線性同餘，中國剩餘定理
  • 這應該是數論裡比較重要的一個部分吧，這類的題目也挺多，具體的内容最好先看看數論書，我也整理過一些，可以參考參考：
  • ​​http://hi.baidu.com/%B1%BF%D0%A1%BA%A2%5Fshw/blog/item/0676025d56a87d4afbf2c093.html​​
  • *簡單題：
  • pku1006 Biorhythms
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=1006​​
  • pku1061 青蛙的約會
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=1061​​
  • pku2891 Strange Way to Express Integers
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=2891​​
  • pku2115 C Looooops
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=2115​​
  • pku2142 The Balance
  • ​​http://162.105.81.212/JudgeOnline/problem?id=2142​​
  • *強烈推薦：
  • sgu106 The equation
  • ​​http://acm.sgu.ru/problem.php?contest=0&problem=106​​
  • pku3708 Recurrent Function （經典）
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=3708​​
  • 5.約瑟夫環問題
  • 這個問題還是比較有意思的，不是很難。
  • *簡單題：
  • pku3517 And Then There Was One
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=3517​​
  • pku1781 In Danger
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=1781​​
  • pku1012 Joseph
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1012​​
  • pku2244 Eeny Meeny Moo
  • ​​http://162.105.81.212/JudgeOnline/problem?id=2244​​
  • *推薦：
  • pku2886 Who Gets the Most Candies?
  • ​​http://162.105.81.212/JudgeOnline/problem?id=2886​​
  • 6.高斯消元法解方程
  • 其實解方程并不是很難，就是按線性代數中學的那種方法，把系數矩陣化成上三角矩陣或數量矩陣，不過有些題目要判斷是否有解，或枚舉所有解。不過這類題目我認為比較難的還是怎麼去建立這個方程組，這個了解了，就沒什麼大問題了。
  • *簡單題：
  • pku1222 EXTENDED LIGHTS OUT
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1222​​
  • pku1681 Painter's Problem
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1681​​
  • pku1830 開關問題
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1830​​
  • *推薦：
  • pku2947 Widget Factory
  • ​​http://162.105.81.212/JudgeOnline/problem?id=2947​​
  • pku2065 SETI
  • ​​http://162.105.81.212/JudgeOnline/problem?id=2065​​
  • *強烈推薦：
  • pku1753 Flip Game
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1753​​
  • pku3185 The Water Bowls
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3185​​
  • *變态題：
  • pku1487 Single-Player Games
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1487​​
  • 7.矩陣
  • 用矩陣來解決問題确實很常見，但我現在用到還不是很好，很多難題我還不會做。建議大家可以去看Matrix67的那篇關于矩陣的十個問題，确實很經典，但不太好看懂。
  • *簡單：
  • pku3070 Fibonacci
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3070​​
  • pku3233 Matrix Power Series
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3233​​
  • pku3735 Training little cats
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3735​​
  • 8.高次同餘方程
  • 有關這個問題我應該是沒什麼發言權了，A^B%C=D，我現在隻會求D和B，唉，很想知道A該怎麼求。就先推薦幾道題目吧，這裡涉及到了一個baby-step，giant-step算法。
  • fzu1759 Super A^B mod C
  • ​​http://acm.fzu.edu.cn/problem.php?pid=1759​​
  • pku3243 Clever Y
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3243​​
  • pku2417 Discrete Logging
  • ​​http://162.105.81.212/JudgeOnline/problem?id=2417​​
  • hdu2815 Mod Tree
  • ​​http://acm.hdu.edu.cn/showproblem.php?pid=2815​​
  • 9.容斥原理，鴿巢原理
  • 很有用的兩個定理，但好像單獨考這兩個定理的不是很多。
  • *鴿巢原理：
  • pku2365 Find a multiple
  • ​​http://162.105.81.212/JudgeOnline/problem?id=2356​​
  • pku3370 Halloween treats
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3370​​
  • *容斥原理：
  • hdu1695 GCD
  • ​​http://acm.hdu.edu.cn/showproblem.php?pid=1695​​
  • hdu2461 Rectangles
  • ​​http://acm.hdu.edu.cn/showproblem.php?pid=2461​​
  • 10.找規律，推公式
  • 這類題目的設計一般都非常巧妙，真的是很難想出來，但隻要找到規律或推出公式，就不是很難了。我很多都是在參考别人思路的情況下做的，能自己想出來真的很不容易。
  • *個人感覺都挺不錯的：
  • pku3372 Candy Distribution
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3372​​
  • pku3244 Difference between Triplets
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3244​​
  • pku1809 Regetni
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1809​​
  • pku1831 不定方程組
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1831​​
  • pku1737 Connected Graph
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1737​​
  • pku2480 Longge's problem
  • ​​http://162.105.81.212/JudgeOnline/problem?id=2480​​
  • pku1792 Hexagonal Routes
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=1792​​
  • 11.排列組合，區間計數，計數序列
  • 這些題目可能需要一些組合數學知識，基本上高中的知識就夠了。區間計數問題一般不難，但寫的時候需要仔細一些，各種情況要考慮到位。至于像卡特蘭數，差分序列，斯特靈數···都還挺有意思，可以去看看《組合數學》。
  • *簡單題：
  • pku1850 Code
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1850​​
  • pku1150 The Last Non-zero Digit
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1150​​
  • pku1715 Hexadecimal Numbers
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1715​​
  • pku2282 The Counting Problem
  • ​​http://162.105.81.212/JudgeOnline/problem?id=2282​​
  • pku3286 How many 0's?
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3286​​
  • *推薦：
  • pku3252 Round Numbers
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3252​​
  • *計數序列：
  • pku1430 Binary Stirling Numbers
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1430​​
  • pku2515 Birthday Cake
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=2515​​
  • pku1707 Sum of powers
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=1707​​
  • 12.二分法
  • 二分的思想還是很重要的，這裡就簡單推薦幾個純粹的二分題。
  • *簡單：
  • pku3273 Monthly Expense
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3273​​
  • pku3258 River Hopscotch
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3258​​
  • pku1905 Expanding Rods
  • ​​http://162.105.81.212/JudgeOnline/problem?id=1905​​
  • pku3122 Pie
  • ​​http://162.105.81.212/JudgeOnline/problem?id=3122​​
  • *推薦：
  • pku1845 Sumdiv
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=1845​​
  • 13.穩定婚姻問題
  • 無意中接觸到這個算法，還蠻有意思的，《組合數學》中有詳細的介紹。
  • pku3487 The Stable Marriage Problem
  • ​​http://acm.pku.edu.cn/JudgeOnline/problem?id=3487​​
  • zoj1576 Marriage is Stable
  • ​​http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1576​​
  • 14.數位類統計問題
  • 在航點月賽中第一次接觸到這類問題，scau大牛little龍推薦我看了一篇論文，09年劉聰的《淺談數位類統計問題》，這篇論文相當精彩，也相當詳細，每道題都有詳細的分析和作者的參考代碼。是以我也沒什麼可說的了，這些題的代碼我部落格裡也就不貼了，大家直接去看論文吧。
  • 簡單：
  • ural1057 Amount of degrees
  • ​​http://acm.timus.ru/problem.aspx?space=1&num=1057​​
  • spoj1182 Sorted bit squence
  • ​​https://www.spoj.pl/problems/SORTBIT/​​
  • hdu3271 SNIBB
  • ​​http://acm.hdu.edu.cn/showproblem.php?pid=3271​​
  • 較難：
  • spoj2319 Sequence
  • ​​https://www.spoj.pl/problems/BIGSEQ/​​
  • sgu390 Tickets
  • ​​http://acm.sgu.ru/problem.php?contest=0&problem=390​​
  • 以上分類的題目在我的部落格裡都可以找到詳細的解題報告和參考代碼，由于比較麻煩就沒加連結，需要的可以用我的站内搜尋找到。
  • 本小結會不斷更新，轉載請注明出處。
  • 嚴重聲明：本文隻适合ACM初學者，路過的大牛如有相同類型的比較好的題目可以推薦一些啊。
  • 來自: http://hi.baidu.com/%B1%BF%D0%A1%BA%A2%5Fshw/blog/item/5305e12c7289973e359bf768.html

​​http://apps.hi.baidu.com/share/detail/15350489​​

1. 對數學類題目小結中的題目的簡單解題報告：
2. 偶然在網上看到某牛人發的數學題目小結，于是拷了回來做，下面每道題目後面注釋的是我寫的簡單解題報告（有些隻是注意事項），而且并非所有都有做，是以希望大家了解，目前正在更新中。
3. //hi.baidu.com/%B1%BF%D0%A1%BA%A2_shw/blog/item/5305e12c7289973e359bf768.html
4. 這裡題目之前有‘ ＃’ 的表示已過，‘ ？’ 表示做了但還沒過。
5. /******************************************************************************************/
6. 1.burnside 定理，polya 計數法
7. 這個大家可以看brudildi 的《組合數學》，那本書的這一章寫的很詳細也很容易了解。最好能完全看懂了，了解了再去做題，不要隻記個公式。
8. * 簡單題：（直接用套公式就可以了）
9. #    pku2409 Let it Bead    // 翻轉時注意珠子為奇偶的情況。
10. //acm.pku.edu.cn/JudgeOnline/problem?id=2409
11. #    pku2154 Color//LTC 的題目，看《具體數學》p141 ，有個化簡的公式。
12. //acm.pku.edu.cn/JudgeOnline/problem?id=2154
13. #    pku1286 Necklace of Beads  // 和2409 一樣
14. //acm.pku.edu.cn/JudgeOnline/problem?id=1286
15. * 強烈推薦：（這題很不錯哦，很巧妙）
16. #    pku2888 Magic Bracelet  // 見月賽解題報告.A[i][j] 為可達矩陣. 而且注意約數的個數範圍。其中矩陣的幂可以預先求出所有matrix[2^i] 出來，然後根據二進制來 求。
17. //162.105.81.212/JudgeOnline/problem?id=2888
18. 2. 置換，置換的運算
19. 置換的概念還是比較好了解的，《組合數學》裡面有講。對于置換的幂運算大家可以參考一下潘震皓的那篇《置換群快速幂運算研究與探讨》，寫的很好。
20. * 簡單題：（應該了解概念就可以了）
21. #    pku3270 Cow Sorting  // 列出置換，然後對于每一個置換循環，不斷用環中的最小的那個和其他的進行換位，可以得到最優。另外還有一種情況就是用整個置換最小的那個和該環進行換位，對于每個環求出這兩個的最小值加起來就可以了。
22. //acm.pku.edu.cn/JudgeOnline/problem?id=3270
23. #    pku1026 Cipher // 先找出所有置換循環，然後對于每一位來計算k% 循環長度後對應于哪個位置,O(n) 複雜度。注意讀寫方面的東西。
24. //acm.pku.edu.cn/JudgeOnline/problem?id=1026
25. * 置換幂運算：
26. #    pku1721 CARDS  // 詳細見05 集訓隊論文《置換群快速幂運算研究與探讨》。
27. //162.105.81.212/JudgeOnline/problem?id=1721
28. #    pku3128 Leonardo's Notebook//
29. 題目意思是：一個置換是否可以由另一個置換的平方得來的。一個置換的平方，原來偶數長的循環會被分裂成兩段長度相等的循環，而奇數長的循環不會被分裂。題目隻是問是否存在，是以隻要看所給置換中偶數長的循環是否成對，否則就不能由一個置換的平方得來。
30. 補充：因為如果所給置換的循環是偶數，則肯定是由分裂過來的，那麼一定是成對的，否則如果是奇數，那麼有可能是原來是奇數，也有可能是原來的偶數分裂成兩個奇數循環。
31. //162.105.81.212/JudgeOnline/problem?id=3128
32. * 推薦：（不錯的應用）
33. #    pku3590 The shuffle Problem  // 把n 分解成若幹個數，使得他們的lcm 最大。在所取的數都是素數幂的時候是最大的，是以可以用遞歸來枚舉所有的分解情況，而且由于要輸出序最小的，是以對于剩下的數可以直接單獨都作為一個循環，這樣就可以使得序最小了。此外，這道題目需要注意求最大的lcm 的時候不能用dp 來做，因為這個具有後效 性，局部最優不一定使得全局最優。
34. //162.105.81.212/JudgeOnline/problem?id=3590
35. 3. 素數，整數分解，歐拉函數
36. 素數是可能數論裡最永恒，最經典的問題了（我們的隊名就叫PrimeMusic^-^ ）。素數的判斷，篩法求素數，大素數的判斷··· 還有很多其他問題都會用到素數。
37. * 最水最水的：（心情不爽時用來解悶吧）
38. #    pku1365 Prime Land
39. #    pku2034 Anti-prime Sequences// 直接搜尋，用DL 優化會快很多。
40. #    pku2739 Sum of Consecutive Prime Numbers
41. pku3518 Prime Gap
42. pku3126 Prime Path
43. pku1595 Prime Cuts
44. pku3641 Pseudoprime numbers
45. pku2191 Mersenne Composite Numbers
46. pku1730 Perfect Pth Powers
47. pku2262 Goldbach's Conjecture
48. pku2909 Goldbach's Conjecture
49. * 篩法：
50. #    pku2689 Prime Distance （很好的一個應用）// 先找出sqrt(2^32) 内的所有素數，然後類似篩選法篩選掉[l,u] 範圍内的數
51. //162.105.81.212/JudgeOnline/problem?id=2689
52. * 反素數：
53. #    zoj2562 More Divisors  //waing... 後記：素數表少打了一個19 ～暈死啊～。。
54. //acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=2562
55. * 素數判斷，整數分解：
56. 這兩題都要用到miller_rabin 的素數判斷和pollard_rho 的整數分解，算法書上都會有，應該是屬于模闆題吧，不過最好看懂自己敲一 遍。
57. #    pku1811 Prime Test  // 學習miller 和pollard 的題目。
58. //acm.pku.edu.cn/JudgeOnline/problem?id=1811
59. #    pku2429 GCD & LCM Inverse  // 分解lcm/gcd 為互質的p,q ，要用到Miller Rabin 和Pollard rho 算法，基本上做出來之後都是模闆題了。
60. //acm.pku.edu.cn/JudgeOnline/problem?id=2429
61. * 歐拉函數：
62. 數論裡很多地方都能用到歐拉函數，很重要的。
63. #    pku1284 Primitive Roots （很水）// 定理：對于奇素數m, 原根個數為phi(phi(m)), 由于phi(m)=m-1, 是以為phi(m-1)
64. //acm.pku.edu.cn/JudgeOnline/problem?id=1284
65. #    pku2407 Relatives （很水）
66. //acm.pku.edu.cn/JudgeOnline/problem?id=2407
67. #    pku2773 Happy 2006  //n 之後的互質的數都是n 之前的加上n 的倍數的。
68. //162.105.81.212/JudgeOnline/problem?id=2773
69. #    pku2478 Farey Sequence （快速求歐拉函數）// 求前n 個歐拉函數的和，用學習指導裡面的n*(1+lnln(n)) 的算法就可以了，非常快。
70. //162.105.81.212/JudgeOnline/problem?id=2478
71. #    pku3090 Visible Lattice Points （法雷級數）
72. //acm.pku.edu.cn/JudgeOnline/problem?id=3090
73. * 推薦：（歐拉函數，費馬小定理）
74. #    pku3358 Period of an Infinite Binary Expansion// 轉化為高次同餘方程。
75. //acm.pku.edu.cn/JudgeOnline/problem?id=3358
76. * 整數分解
77. 這個也很重要的耶，包括大數的表示方法。
78. #    pku2992 Divisors// 注意預處理，有很多組資料.
79. //acm.pku.edu.cn/JudgeOnline/problem?id=2992
80. ?    fzu1753 Another Easy Problem// 記得n! 有多少個p 的幂是怎麼求的。
81. //acm.fzu.edu.cn/problem.php?pid=1753
82. hit2813 Garden visiting
83. //acm-hit.sunner.cn/judge/show.php?Proid=2813
84. ?    pku3101 Astronomy （分數的最小公倍數）// 高精度gcd ，逾時中。
85. //acm.pku.edu.cn/JudgeOnline/problem?id=3101
86. 4. 擴充歐幾裡得，線性同餘，中國剩餘定理
87. 這應該是數論裡比較重要的一個部分吧，這類的題目也挺多，具體的内容最好先看看數論書，我也整理過一些，可以參考參考：
88. //hi.baidu.com/%B1%BF%D0%A1%BA%A2%5Fshw/blog/item/0676025d56a87d4afbf2c093.html
89. * 簡單題：
90. #    pku1006 Biorhythms // 注意最後結果為0 或負數的情況
91. //acm.pku.edu.cn/JudgeOnline/problem?id=1006
92. #    pku1061 青蛙的約會
93. //acm.pku.edu.cn/JudgeOnline/problem?id=1061
94. #    pku2891 Strange Way to Express Integers  //x==a1(mod m1),x==a2(mod m2), 兩個方程可以求出x ，然後重新令a1 為求出的解x,m1=lcm(m1,m2) ，然後繼續和後面的進行求解。注意資料運算過程中可能溢出的問題。
95. //acm.pku.edu.cn/JudgeOnline/problem?id=2891
96. #    pku2115 C Looooops
97. //acm.pku.edu.cn/JudgeOnline/problem?id=2115
98. #    pku2142 The Balance // 枚舉，x=x0+b/d*t ，直到x>min(x+y)
99. //162.105.81.212/JudgeOnline/problem?id=2142
100. * 強烈推薦：
101. #    sgu106 The equation // 求ax+by=c 的時候，考慮a,b 為零的特殊情況，此外，若a,b 不是非負數，那麼擴充歐幾裡德會有問題，于是我們可以把求x,y 變為求 x'=-x,y'=-y ，此時a,b, 就可以變為非負數來處理，同時x',y' 的範圍也要相應取反。而且在取得區間時候，要注意區間邊緣要進行相應的取 整。後記：要用cin,cout 才能AC ，用printf 會wa 。。。極度無奈中，偶然才發現的～_ ～!
102. //acm.sgu.ru/problem.php?contest=0&problem=106
103. #    pku3708 Recurrent Function （經典）// 具體數學第一章。對于每一位求出循環節m1 ，還有該位從m 達到k 最少要經過r1 次标号變化，于是就可以得到x==r1 (mod m1) ，然後同樣的方法求其他的位，接着就可以兩兩方程這樣解中國剩餘定理。
104. //acm.pku.edu.cn/JudgeOnline/problem?id=3708
105. 5. 約瑟夫環問題
106. 這個問題還是比較有意思的，不是很難。
107. * 簡單題：
108. #    pku3517 And Then There Was One
109. //acm.pku.edu.cn/JudgeOnline/problem?id=3517
110. #    pku1781 In Danger
111. //acm.pku.edu.cn/JudgeOnline/problem?id=1781
112. #    pku1012 Joseph // 考慮剩下k+1 個人，那麼上一個出局的人肯定是壞人，是以考慮接下來一定要最後一個壞人出局，是以m==0 或1(mod k+1) 。然後枚舉m ，再驗證。
113. //162.105.81.212/JudgeOnline/problem?id=1012
114. #    pku2244 Eeny Meeny Moo
115. //162.105.81.212/JudgeOnline/problem?id=2244
116. * 推薦：
117. #    pku2886 Who Gets the Most Candies?// 線段樹+ 反素數。
118. //162.105.81.212/JudgeOnline/problem?id=2886
119. 6. 高斯消元法解方程
120. 其實解方程并不是很難，就是按線性代數中學的那種方法，把系數矩陣化成上三角矩陣或數量矩陣，不過有些題目要判斷是否有解，或枚舉所有解。不過這類題目我認為比較難的還是怎麼去建立這個方程組，這個了解了，就沒什麼大問題了。
121. * 簡單題：
122. #    pku1222 EXTENDED LIGHTS OUT  // 解異或運算的方程。n*m 個方程和未知數。
123. //162.105.81.212/JudgeOnline/problem?id=1222
124. #    pku1681 Painter's Problem
125. //162.105.81.212/JudgeOnline/problem?id=1681
126. #    pku1830 開關問題  // 以上三題做法都一樣。
127. //162.105.81.212/JudgeOnline/problem?id=1830
128. * 推薦：
129. #    pku2947 Widget Factory  // 最好要化成嚴格的階梯型，友善判解。而且模某個數的時候解方程要用到擴充歐幾裡德算法。
130. //162.105.81.212/JudgeOnline/problem?id=2947
131. #    pku2065 SETI// 與上題一樣。
132. //162.105.81.212/JudgeOnline/problem?id=2065
133. * 強烈推薦：
134. #    pku1753 Flip Game // 資料範圍比較小，枚舉可過。如果用高斯消元做，那麼對于多解的時候也是需要枚舉的，而且這種類型不具有太大的擴充性，這裡高斯消元不見的比枚舉要優越。
135. //162.105.81.212/JudgeOnline/problem?id=1753
136. #    pku3185 The Water Bowls // 同樣如果對于無數解的時候，就需要對解進行枚舉。其實這道題目可以先枚舉第一位是否需要翻轉，然後其他的就已經确定了，不過需要注意如果第一位翻轉的時候，答案别忘了加上去，我因為這個搞了好久～～～郁悶。
137. //162.105.81.212/JudgeOnline/problem?id=3185
138. // 同類題目，我自己加上去的。
139. pku1395
140. pku2055
141. ural1561
142. pku3254
143. * 變态題：
144. pku1487 Single-Player Games
145. //162.105.81.212/JudgeOnline/problem?id=1487
146. 7. 矩陣
147. 用矩陣來解決問題确實很常見，但我現在用到還不是很好，很多難題我還不會做。建議大家可以去看Matrix67 的那篇關于矩陣的十個問題，确實很經典， 但不太好看懂。
148. * 簡單：
149. pku3070 Fibonacci
150. //162.105.81.212/JudgeOnline/problem?id=3070
151. pku3233 Matrix Power Series
152. //162.105.81.212/JudgeOnline/problem?id=3233
153. pku3735 Training little cats
154. //162.105.81.212/JudgeOnline/problem?id=3735
155. 8. 高次同餘方程
156. 有關這個問題我應該是沒什麼發言權了，A^B%C=D ，我現在隻會求D 和B ，唉，很想知道A 該怎麼求。就先推薦幾道題目吧，這裡涉及到了一個baby- step ，giant-step 算法。
157. #    fzu1759 Super A^B mod C  //a^b%c=a^(b%phi(c))%c , 注意a==c 的情況，
158. //acm.fzu.edu.cn/problem.php?pid=1759
159. #    pku3243 Clever Y  // 和上面差不多，不過c 不一定是素數，是以方法就是解出a^m*x+c*y=gcd(a^m,c) 的所有解來判斷，若無解則不管，因為c 不是素數可能 a^m 沒有逆。
160. //162.105.81.212/JudgeOnline/problem?id=3243
161. #    pku2417 Discrete Logging  //hash ，最直接的離散對數
162. //162.105.81.212/JudgeOnline/problem?id=2417
163. ？    hdu2815 Mod Tree // 逾時中，時限好像挺緊的。
164. //acm.hdu.edu.cn/showproblem.php?pid=2815
165. #    sgu261 求A   wa test 23.. 後記：原來是hash 有錯誤，因為用了vector 後是從0 開始的，而我判斷hash 連結清單結束的是0 ，如果恰好最後一個是在vector 的0 位 置，那麼就會忽略掉這個資料，是以就會出現找不到那個數的情況。另外進行最後答案輸出的時候，vector 的size （）是傳回unsigned int 的，如果size( ）是0 ，那麼size()-1 就是2^32-1 了，是以這裡就需要特别注意。
166. ? http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemId=3538 //handling... 還沒有找出更好的方法解決當a 和p 不互質情況下的解法。
167. ​​http://202.120.80.191/problem.php?problemid=2700​​
168. 9. 容斥原理，鴿巢原理
169. 很有用的兩個定理，但好像單獨考這兩個定理的不是很多。
170. * 鴿巢原理：
171. #    pku2356 Find a multiple // 同下。
172. //162.105.81.212/JudgeOnline/problem?id=2356
173. #    pku3370 Halloween treats////n 個數，尋找c 個(c<=n) ，使得他們的和為c 的倍數。由抽屜原理，前n 個數的 mod c 肯定有重複的，那麼一定存在一個區間使得他們的和是c 的倍數。
174. //162.105.81.212/JudgeOnline/problem?id=3370
175. * 容斥原理：
176. #    hdu1695 GCD // 求gcd(x,y)=k 的個數，相當于求gcd(x/k,y/k)=1 的個數，其中x/k 在[a/k,b/k],y/k 在[c/k,d/k] 之間。所 以就是求在一定區間内，x ，y 互質的對數。假設b<d, （此處b,d 已除k ）那麼對于<=b, 直接用歐拉函數就可以了，對于[b+1,d] 之 間的數，對于每一個分解質因數，然後利用容斥原理，求出［1,b ］之間和這個數互質的個數。注意最後答案可能超過int ，用I64d 輸出。
177. //acm.hdu.edu.cn/showproblem.php?pid=1695
178. #    hdu2461 Rectangles // 對稱情況下才能使用懶标記，而且覆寫的标号不向下傳。另外在pku3695 上同樣的題目由于時限很緊，是以可以對坐标進行離散化。log1000 和 log40 還是有差别的。
179. //acm.hdu.edu.cn/showproblem.php?pid=2461
180. 10. 找規律，推公式
181. 這類題目的設計一般都非常巧妙，真的是很難想出來，但隻要找到規律或推出公式，就不是很難了。我很多都是在參考别人思路的情況下做的，能自己想出來真的很不容易。
182. * 個人感覺都挺不錯的：
183. #    pku3372 Candy Distribution// 找規律。。。其實可以進行分析的。
184. //162.105.81.212/JudgeOnline/problem?id=3372
185. #    pku3244 Difference between Triplets// 這道題目要用到一個很巧妙的轉化，把比較轉化為絕對值的計算。因為max(a,b,c)-min(a,b,c)=(|a- b|+|a-c|+|b-c|)/2, 然後剩下的就容易做了。
186. //162.105.81.212/JudgeOnline/problem?id=3244
187. pku1809 Regetni
188. //162.105.81.212/JudgeOnline/problem?id=1809
189. pku1831 不定方程組
190. //162.105.81.212/JudgeOnline/problem?id=1831
191. #    pku1737 Connected Graph //f[n] 為n 個點的聯通數，那麼f[n]=2^(c[n][2])-sigma(f[k]*c[i-1][k-1]*2^(c[n-k][2]))
192. //162.105.81.212/JudgeOnline/problem?id=1737
193. #    pku2480 Longge's problem//sigma(gcd(i,n))=sigma(d|n && d*[gcd(i,n)==d]), 枚舉所有n 的約數d ，然後對于n/d ，找出所有和n/d 互質的數的個數就是gcd(i,n)==d 的個數，進而用歐拉 函數解決。
194. //162.105.81.212/JudgeOnline/problem?id=2480
195. pku1792 Hexagonal Routes
196. //acm.pku.edu.cn/JudgeOnline/problem?id=1792
197. 11. 排列組合，區間計數，計數序列
198. 這些題目可能需要一些組合數學知識，基本上高中的知識就夠了。區間計數問題一般不難，但寫的時候需要仔細一些，各種情況要考慮到位。至于像卡特蘭數，差分序列，斯特靈數··· 都還挺有意思，可以去看看《組合數學》。
199. * 簡單題：
200. pku1850 Code
201. //162.105.81.212/JudgeOnline/problem?id=1850
202. pku1150 The Last Non-zero Digit
203. //162.105.81.212/JudgeOnline/problem?id=1150
204. pku1715 Hexadecimal Numbers
205. //162.105.81.212/JudgeOnline/problem?id=1715
206. pku2282 The Counting Problem
207. //162.105.81.212/JudgeOnline/problem?id=2282
208. pku3286 How many 0's?
209. //162.105.81.212/JudgeOnline/problem?id=3286
210. * 推薦：
211. pku3252 Round Numbers
212. //162.105.81.212/JudgeOnline/problem?id=3252
213. * 計數序列：
214. pku1430 Binary Stirling Numbers
215. //162.105.81.212/JudgeOnline/problem?id=1430
216. pku2515 Birthday Cake
217. //acm.pku.edu.cn/JudgeOnline/problem?id=2515
218. pku1707 Sum of powers
219. //acm.pku.edu.cn/JudgeOnline/problem?id=1707
220. 12. 二分法
221. 二分的思想還是很重要的，這裡就簡單推薦幾個純粹的二分題。
222. * 簡單：
223. pku3273 Monthly Expense
224. //162.105.81.212/JudgeOnline/problem?id=3273
225. pku3258 River Hopscotch
226. //162.105.81.212/JudgeOnline/problem?id=3258
227. pku1905 Expanding Rods
228. //162.105.81.212/JudgeOnline/problem?id=1905
229. pku3122 Pie
230. //162.105.81.212/JudgeOnline/problem?id=3122
231. * 推薦：
232. #    pku1845 Sumdiv // 令a=p1^m1 * p2^m2 * ... * pk^mk, 那麼由于因數和是一個積性函數,
233. 是以 f(a)=f(p1^m1)*f(p2^m2)*..  ; f(x^t)=1+x+x^2+..+x^t=(1-x^(t+1))/(1-x);
234. 由于mod 某個數，是以可以1/(1-x) 可以用同餘數解決。不過注意如果MOD | x-1, 那麼 f(x^t)=t+1 特殊處理一下。
235. //acm.pku.edu.cn/JudgeOnline/problem?id=1845
236. 13. 穩定婚姻問題
237. 無意中接觸到這個算法，還蠻有意思的，《組合數學》中有詳細的介紹。
238. pku3487 The Stable Marriage Problem
239. //acm.pku.edu.cn/JudgeOnline/problem?id=3487
240. zoj1576 Marriage is Stable
241. //acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=1576
242. 14. 數位類統計問題
243. 在航點月賽中第一次接觸到這類問題，scau 大牛little 龍推薦我看了一篇論文，09 年劉聰的《淺談數位類統計問題》，這篇論文相當精彩，也相當詳 細，每道題都有詳細的分析和作者的參考代碼。是以我也沒什麼可說的了，這些題的代碼我部落格裡也就不貼了，大家直接去看論文吧。
244. 簡單：
245. ural1057 Amount of degrees
246. //acm.timus.ru/problem.aspx?space=1&num=1057
247. spoj1182 Sorted bit squence
248. //www.spoj.pl/problems/SORTBIT/
249. hdu3271 SNIBB
250. //acm.hdu.edu.cn/showproblem.php?pid=3271
251. 較難：
252. spoj2319 Sequence
253. //www.spoj.pl/problems/BIGSEQ/
254. sgu390 Tickets
255. //acm.sgu.ru/problem.php?contest=0&problem=390
256. 以上分類的題目在我的部落格裡都可以找到詳細的解題報告和參考代碼，由于比較麻煩就沒加連結，需要的可以用我的站内搜尋找到。
257. 本小結會不斷更新，轉載請注明出處。
258. 歐拉函數。
259. # pku 3696 The Luckiest number
260. //(10^n-1+..+10+1)=(10^n-1)/9, 歐拉函數，離散對數，注意溢出處理（相乘時變為aT+b ）。
261. //acm.pku.edu.cn/JudgeOnline/problem?id=3696
262. 樹狀數組
263. # hdu 3333
264. 先求出每個位置後面和它一樣的最近的那個數的位置next[i] ，然後用樹狀數組記錄不重複的前n 個數的和，接着對詢 問區間排序，從左到右做，記left 為在目前區間左邊的那些數，通過樹狀數組，将left 到next[left]-1 之間的所有的數都減去 val[left] ，然後就可以直接像sum[i]-sum[j] 那樣友善的求出區間裡面沒有重複的數的和。
265. ​​http://acm.hdu.edu.cn/showproblem.php?pid=3333​​
266. # pku 3222 // 樹的dfs 和分治思想
267. 解題報告見此：http://acm.pku.edu.cn/JudgeOnline /showmessage?message_id=129459
  1. pku 1150 The Last Non-zero Digit
  2. 和計算排列數末尾有多少個零有些類似，把2，5因子都拿出來，剩下的數的最後一個數字隻有1，3，7，9。隻有各位上的數字才會影響最後一個非零數字。統計可以用遞歸來統計，求出1～n中因子2，5的個數，以及3，7，9結尾的數和去掉2，5後新的到的數中3，7，9結尾的數。結果就是 2^(dig[2]-dig[5])*3^(dig[3])*7^(dig[7])*9^(dig[9])  mod 10 ，用快速幂乘來算。
  3. pku 1186 方程的解數 (hash,枚舉)
  4. 題目給出最多有6個未知數，未知數的取值在[1,150]之間，直接枚舉時間複雜度是150^6，這個時間不能接受。枚舉前一半的未知數可以到達的值(用hash表儲存)，再枚舉後一半，這樣可以加快枚舉。
  5. pku 1285 Combinations, Once Again（有重複的組合，dp）
  6. 對輸入的數先統計一下，每個數出現的次數。如果每次重複的數，輸出c[n][m]就可以。有重複數時，要考慮到取相同元素的情況，那麼ans=sigma c[x][i]*z[s][m-i]  0<i<=m z[i][j]表示從1到第i堆中拿j個，把重複的數字表示成a[1],a[2]..,a[s],s個數出現重複。注意幾個邊界條件，c[0][0]=1,z[1][0...a[1]]=1,z[i][1]=i 2<=i<=s。
  7. pku 1430 Binary Stirling Numbers (stirling 數)
  8. 在wiki上找到公式，原來mod 2時群組合數有關系。原文如下：
  9. Using a Sierpiński triangle, it's easy to show that the parity of a Stirling number of the second kind is equal to the parity of a related binomial coefficient:
  10. Or directly, let two sets contain positions of 1's in binary representations of results of respective expressions:
  11. then mimic a bitwise AND operation by intersecting these two sets:
  12. to obtain the parity of a Stirling number of the second kind in O(1) time.
  13. pku 1465 Multiple(BFS,整除)
  14. 給幾個一些數學，找出由這些數字組成的數中最小的一個能整除n的數。0<n<4999,把所有的數從小到大開始，在入隊列前看下該數所到達的餘數是否被前面小的數求到過，若否才入隊。這樣搜尋的空間就隻有n的剩餘系了。
  15. pku 1715 Hexadecimal Numbers(組合)
  16. 不重複的組合問題，知道第幾個找出這個組合。從最高位開始，一位一位确定dfs下去，每次都要保證已确定的位的所有組合不少于題目給出的序号。最多八層。
  17. pku 1737 Connected Graph(組合數學，高精度)
  18. 題目是求n個點用邊連結，形成聯通圖的方案總算。滿足聯通的邊數在[n-1,n(n-1)/2],自己一開始想分邊數情況考慮，發現情況比較複雜，推出一個像整數拆分的方法。還來在網上看到一種更好的解法。公式是f[n]=f[k]*f[n-k]*c[n-2][k-1]*((2^k)-1) (c[n-2][k]表示組合數,1<=k<n);考慮一個完整的聯通圖，可以标記兩個點1，2。将點1，點2分别劃分在兩個子聯通圖中分别為g1，g2。在g1中最少要有一個點與g2中的點2連結。這樣的方式共2^k-1中，而g1總有c[n-2][k-1]個。将他們乘在一起就有了上面的式子。另外這題要用到高精度，終于用java寫了個高精度的題感覺真友善。
  19. pku 1845 Sumdiv(積性函數，因子和)
  20. 求a^b的因子和(包括1和a^b),由于因子和是積性函數。是以f(a^b)=f(p1^t1)*f(p2^t2)...*f(pn^tn),對于f(p^t)的情況:
  21. f(p^t)=1+p+p^2+...+p^t=(p^(t+1)-1)/p-1。題目還要求mod 9901,這雖然是個素數，但是資料中出現了p-1 = 0 (mod 9901)的情況，這時f(p^t)=t+1 (mod 9901),要特殊處理下，其餘用快速幂乘。
  22. pku 1809 Regetni（奇偶，組合）
  23. 根據 這個公式計算 A=|x1y2 - y1x2 + x2y3 - y2x3 + x3y1 - y3x1|/2 三角形的面積是否為整數。這題不要去算具體的面積，答案和所選點的奇偶性有關，點的隻有4種類型，(0,0),(1,1),(1,0),(0,1)。把這4類點的所有組合情況(共20種)代入公式
  24. 發現，當最少有兩個點屬于同一類型是面積才是整數。那麼隻有統計出所有點的組合情況就可以得出答案了。點的組合情況
  25. {0,1,2},{0,1,3},{0,2,3},{1,2,3},{0,1,1},{0,2,2},{0,3,3},{1,0,0},{1,2,2},{1,3,3},{2,0,0},{2,1,1},{2,3,3},
  26. {3,0,0},{3,1,1},{3,2,2},{0,0,0},{1,1,1},{2,2,2},{3,3,3} 這些是合理的組合。
  27. pku 1831 不定方程組(構造解)
  28. 這個題目很有意思，說a1+a2..an=s,1/a1+1/a2....+1/an=1;求一組這樣的解。
  29. 為了找S的一組解，可以把S變小，來得到S的解。兩種變小的方法:p/2+1/2=1 ,p*2+2=S;或p/2+1/3+1/6=1,p*2+9=S;選這兩種方式是為了使奇數，偶數都有變小的方法。更重要的是當S一定大時，一定會有解。證明可以通過歸納來證得。是以事先保留一些小的S的解。大的S通過遞歸的構造出解來。
  30. pku 2142 The Balance(不定方程)
  31. '*x+b'*y=d'，一般解為x=x0-b'*t,y=y0+a't;其中t為任意整數。
  32. pku 2154 Color(波利亞定理,着色問題)
  33. 一個經典的着色問題，題目描述的是一個正常的旋轉群，它的輪換名額為1/n*sigma(euler(d)*(xd)^(n/d)) ，其中d為n的所有因子。有了這個生成函數就可以容的計算n種顔色，在正n邊形上着色的不同方案數了。
  34. pku 3352 In Danger(約瑟夫環)
  35. 簡單題，和具體數學第一章提到的問題是一樣的，講每數2去掉一人，求勝利人的編号。公式是
  36. f(n)=f(n/2)*2-1 n=2*k
  37. f(n)=f(n-1/2)*2+1  n=2*k+1
  38. pku 2282 The Counting Problem(計數統計)
  39. 一個計算問題，統計a,b之間0-9這些數字出現的次數。可以分别計算f(b),f(a-1)的大小,其中 a<b f(n)表示1到n數字出現的統計。對于f(n) ，可以按位計算，從個位到n的最高位，分别計算0-9的個數，0的計算有些特殊，因為0不能是一個數字的最高位
  40. while(a>=times)
  41. {
  42. len=a/(times*10);
  43. for(i=0;i<10;i++)aa[i]+=len*times;
  44. if(len>0)aa[0]-=times;
  45. tmp=(a/times)%10;
  46. if(a>=times*10)start=0;else start=1;
  47. for(i=start;i<tmp;i++)aa[i]+=times;
  48. aa[tmp]+=a%times+1;
  49. times*=10;
  50. }
  51. pku 2429 gcd lcm Inverse
  52. 大數分解，要分解的數很大，到了2^63,普通的素數表方法行不通，要使用Pollard分解，分解lcm/gcd。需要注意的是會出現lcm==gcd的情況。
  53. pku 2769 Reduced ID Numbers(同餘)
  54. 給出n個數，找一個數p,使得沒個數mod p的值不相等。即n個數mod p不同餘。先求出任意兩個數的差(要正的),找個最小的數，使其不是前面求的差的約數。
  55. pku 2891 Strange Way to Express Integers(解模線性方程組)
  56. 這題是解個同餘方程組，既解x= ai (mod bi) ,題目沒有保證bi之間兩兩互素，是以中國剩餘定理，在這裡沒用。可以通過先求
  57. 兩個方程的解，這樣就将兩個方程和并成一個，直達隻剩下一個為止就可以的到答案了。在合并的過程中有不能合并的情況出現就
  58. 說明整個方程組沒有解。c=a1 (mod b1),c=a2 (mod b2)  c=a1+b1*x, a1+b1*x= a2 (mod b2),用擴充歐幾裡德求出c。兩個方程就
  59. 可以用 c'= c (mod lcm(b1,b2))表示。
  60. hdu 1792 A New Change Problem
  61. 題是說：給兩個互質的數，要求出兩個數所不能組合出的正整數。在較大數的每一個等價類中找出最小的一數，它是較小數的倍數，那麼在這個等價類中小于這個數的都是不能被表示出來的。最大的一個不能被表示出來的數是(n-1)*m-n 其中n>m,由于n有n個等價類，一個類包含不可表示出的數是m-1,總是是(n-1)*(m-1)/2
  62. pku 2888 Magic Bracelet(帶限制的着色問題)
  63. 這題還是要用到波利亞定理，唯一的不同是計算矩陣的幂模，再求矩陣的迹。具體的推導就不知道是怎麼來的。關于矩陣是指允許相鄰的兩種顔色之間有邊，這就形成了個無向圖。矩陣的n幂模，和快速幂乘的原理是一樣的。
  64. pku 2917 Diophantus of Alexandria(不定方程，因數分解)
  65. 模拟下後發現，滿足1/x+1/y=1/z的x，y是z的約數，并且x，y互素。統計x，y的對數再加1（x=z,y=z是特殊的一對）。
  66. 後來看到讨論裡有公式，(x-z)(y-z)=z^2,計算小于z，并是z^2的約數就是答案了。
  67. pku2992 Divisors (組合數，因子個數)
  68. 計算C(n,k)的因子個數,由于n很小，最大為431，是以可以把1～431的所有數先因式分解，再來統計n*(n-1)...(n-k+1)/k*(k-1)...1的素因子個數。
  69. pku 3370 Halloween treats(鴿巢原理)
  70. 給定m個整數a1,a2,a3,..,am,存在整數k和l，0<=k<l<=m,使得ak+1 + ak+2 + ... +al能夠被m整除。也就是說存在連續的一段al,...am,之和被m整除。考慮從a1...ai的和si，必定有si%m==0 或 si = sj (mod m),這種情況下取ai+1...aj,這段之和會是m的倍數。
  71. pku 3128 Leonardo's Notebook(置換)
  72. 題目意思是：一個置換是否可以由另一個置換的平方得來的。一個置換的平方，原來偶數長的循環會被分裂成兩段長度相等的循環，而奇數長的循環不會被分裂。題目隻是問是否存在，是以隻要看所給置換中偶數長的循環是否成對，否則就不能由一個置換的平方得來。
  73. pku 3244 Difference between Triplets(公式變形)
  74. 很巧妙的公式變形，可惜不自己想出來的。首先計算max(a,b,c)-min(a,b,c)=(|a-b|+|b-c|+|a-c|)/2,有了這個公式就可以把比較變成加。那麼
  75. D(Ta, Tb) = max {Ia − Ib, Ja − Jb, Ka − Kb} − min {Ia − Ib, Ja − Jb, Ka − Kb}
  76. =(|Ia-Ib-Ja+Jb|+|Ja-Jb-Ka+Kb|+|Ia-Ib-Ka+Kb|)/2
  77. 令Ia-Ja=Wa,Ja-Ka=Ua,Ia-Ka=Ha;
  78. =(|Wa-Wb|+|Ua-Ub|+|Ha-Hb|)
  79. 将讀入的資料轉化W,U，H三個數組，分别計算這三個數組任意兩個元素的差的絕對值之和。這裡要用小于O(n^2)的算法，把數組排序後可以拿掉絕對值，統計每個元素作為減數出現的次數。
  80. pku 3324 Lucas-Lehmer Test(模運算)
  81. 首先要用到高精度，用java很友善。在計算模的時候，由于是mod 2^p-1,可以用移位來加速。
  82. a=r (mod 2^p-1) => a=k*(2^p-1)+r,先算個打概的k,得到的r>2^p-1,繼續減2^p-1。這樣比直接模運算要快。
  83. pku 3372 Candy Distribution(二次剩餘系)
  84. 根據題目的意思可以得到方程 1+n(n+1)/2 =a (mod N),顯然這是一個二次模方程。要看N的二次完全剩餘系是否都有解。
  85. 結論是N要是2^x,x>=0,結論的證明還不知道。
  86. pku 3516 Hide That Number（高精度）
  87. 題目是說給出一個數y，找到 x*11= y (mod 10^length(y)),如果y很小，直接求出逆來就能得到答案了，可是y很大，構造的方法沒有想到，最後還是暴力做的。每次在y的前面加個數學(1,2..9),或是加上10這兩個數字，看新得到的數字是11的倍數。若是，就可以得到答案了。由于y很大，普通的高精度會逾時，要增加進制。
  88. pku 3847 The Stable Marriage Problem（穩定婚姻）
  89. 穩定婚姻問題。用到了延遲認可算法。用最優方提出比對，而被比對者，不會立即接受，而是在提出要求者的集合中去掉，比目前着差的元素，知道沒有人提出比對，被比對者才确定下比對關系。值得一提的是，穩定婚姻的存在性不能被保證。
  90. pku 3358 Period of an Infinite Binary Expansion(數論，歐拉定理)
  91. 這個題目是求兩個數相除p/q，結果的小數部分用二進制表示，當q不是2的幂時，這個二進制是個無線循環的01串。
  92. 下面是個模拟小數部分按二進制表示，可以發現二進制傳一定會有循環，因為p=p%q,既然是循環，又是模運作，這和p模q的階有關，p%q的階一定是q的歐拉函數的因子。這樣轉換成一個模方程:p*2^n = x(mod q),當然p和q要互素，2和q互素。在計算前把q中的2去掉，p，q同除最大公因數。然後從1開始枚舉，是以的歐拉數的因子。
  93. #include <stdio.h>
  94. #define pr printf
  95. int main()
  96. {
  97. int i,p,q;
  98. while(scanf("%d%d",&p,&q)==2){
  99. "0.");
  100. for(i=1;i<=100;i++)
  101. {
  102. p*=2;
  103. "%d",p/q);
  104. p=p%q;
  105. }
  106. "/n");
  107. }
  108. }
  109. /*
  110. 5 192
  111. 0.000001101010101010101010101010101010101010101010101010101010101010101010101010
  112. 1010101010101010101010
  113. */
  114. pku 3590 The shuffle Problem(置換，數的分解)
  115. 題目求一個排列通過置換之後再回到原來的那個排列，對于給定的排列求出一個滿足置換次數最多的一個置換。一個置換可以分解成多個循環，每次置換元素之和在同一個循環中的元素發生轉換，同一個循環中循環節是元素的個數，是以這個題是要把一個數分成多個數的和，讓這些數的最小公倍數最大。要保證lcd最大應該分解出來的每個數兩兩互素。由于數比較小，23是能最大的素數，是以直接枚舉可以滿足。
  116. pku 3641 Pseudoprime numbers(費馬定理，快速幂乘)
  117. 簡單題，先看p是否是素數，若是直接輸出no。否則計算(a^p)%p,若結果是a輸出yes，否則輸出no。
  118. 2008哈爾濱賽區網絡預選1007 The Luckiest number（歐拉定理運用）
  119. 題目說要找個數t，它的數字全是8，對于給定的n，t要是n的整數倍，求最小的t。
  120. 賽後才發現這題并不拿，可能是我太菜了。這題問題可以轉換成8*(10^x-1)/9 = 0 (mod n ),這樣就可以看出還有因子5和16的n是沒有解的。并且n是偶數時，其解是n除去2因子的解。最後就是求解 10^x = 1 (mod 9*n)  n是一個奇數，是以(10,n)=1,這樣就可以根據歐拉定理 ,滿足等式的解隻能是 euler(9*n)的因子。枚舉歐拉數的因子，最小的那個就是要求的解。由于n可以到2000000000，快速幂乘要支援64位運算。
  121. 2008 成都網絡預選 1005 Farey Sequence Again(Farey Sequence ,構造)
  122. 與其說是數學題，還不如說是個模拟題。Farey Sequence序列規律性很強，暴力模拟後發現有很多規律。要用到的一個性質是
  123. Fn中連續的3個元素，a1/b1 ,a2/b2,a3/b3。若a1+a3<n 并且 b1+b3<=n ,則 a2=a1+a3,b2=b1+b3。這個性質很有用，根據它可以推出序列中前n項的分子不超過3，而且在構造的時候也要用到這個性質，找個第一個分母是2和3的元素的位置，都可以通過觀察看出規律。序列就分成了3段，第一段分子隻有1，第二段分子有1和2，而且是2，1，2，1，2，。。。這樣循環的。第三段有1，2，3，也會出現循環，或是3，1，3，2 或是3，2，3，1這樣的循環結。是以的規律都可以在模拟的序列中看出。隻有3為分子時看不出規律，但是這樣的元素左右兩個一定是分子為1和2的兩個元素，根據性質，知道3周圍的兩個元素的分母，就可以得出分子為3的元素的分母
  124. 2008 哈爾濱現場賽  Simple Addition Expression hdu2451
  125. 通過讀題發現滿足要求的數字，最高位由1，2，3組成，最低位由0，1，2組成，中間由0，1，2，3組成。計算小于n的數有多少個這種數就是答案。
  126. 2008 哈爾濱現場賽 K-dimension number hdu2447
  127. 讀題後發現K要麼是p,要麼是p^2 (p為素數)，且p<=97,K維數n的情況隻有三種。
  128. 一，當k為p時，n=(p')^(p-1)
  129. ')^(p-1)*(p2')^(p-1)或n=(p1')^(p^2-1)
  130. 三，當k為1是，n=1。
  131. zoj 2562 More Divisors(反素數，dp)
  132. 反素數是指在不大于n數中含有最多約數，值最小的一個，比如2，4，6。。都是反素數。題目要求在小于10^16中的反素數。
  133. 由于反素數要求約數盡量多，是以素因子個數要盡量少，而指數要盡量大，這樣一個數成為反素數的機會就大。是以隻要考慮前13個素數所能組成的數就可以。轉移方程
  134. f[i][j]= min{f[i-1][j/(k+1)]*p(i)^k}
  135. f[i][j] 表示i個素數，有j個約數的最小值。p(i)表示第i個素數,j%(k+1)==0
  136. 要注意的地方: j不超過50000。
php 組合數學 整數分解
上一篇: 高等數學筆記第二天
下一篇: 高等數學筆記第五天

繼續閱讀