POJ數學（ZZ）

好好練~~

1.burnside定理，polya計數法

    這個大家可以看brudildi的《組合數學》，那本書的這一章寫的很詳細也很容易了解。最好能完全看懂了，了解了再去做題，不要隻記個公式。

    *簡單題：（直接用套公式就可以了）

    pku2409 Let it Bead   

   http://acm.pku.edu.cn/JudgeOnline/problem?id=2409

    pku2154 Color

   http://acm.pku.edu.cn/JudgeOnline/problem?id=2154

    pku1286 Necklace of Beads

   http://acm.pku.edu.cn/JudgeOnline/problem?id=1286

    *強烈推薦：（這題很不錯哦，很巧妙）

    pku2888 Magic Bracelet

   http://162.105.81.212/JudgeOnline/problem?id=2888

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/ С _shw/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