原文链接:  .coms nhaowenprimeitemd7faf6ea35b6dee4fb42ba2a 1.b rnside 定理,polya 计数法 这个大家可以看br dildi 的"组合数学",那本书的这一章写的很详细也很容易理解.最好能完全看懂了,理解了再去做题,不要只记个公式. * 简单题:(直接用套公式就可以了) # pk 2409 let it bead  翻转时注意珠子为奇偶的情况.  .ed .cnj dgeonlineproblem?2409 # pk 2154 colorltc 的题目,看"具体数学"p141 ,有个化简的公式.  .ed .cnj dgeonlineproblem?2154 # pk 1286 necklace of beads  和2409 一样  .ed .cnj dgeonlineproblem?1286 * 强烈推荐:(这题很不错哦,很巧妙) # pk 2888 magic bracelet  见月赛解题报告.a[i][j] 为可达矩阵. 而且注意约数的个数范围.其中矩阵的幂可以预先求出所有matrix[2^i] 出来,然后根据二进制来 求.  dgeonlineproblem?2888 2. 置换,置换的运算 置换的概念还是比较好理解的,"组合数学"里面有讲.对于置换的幂运算大家可以参考一下潘震皓的那篇"置换群快速幂运算研究与探讨",写的很好. * 简单题:(应该理解概念就可以了) # pk 3270 cow sorting  列出置换,然后对于每一个置换循环,不断用环中的最小的那个和其他的进行换位,可以得到最优.另外还有一种情况就是用整个置换最小的那个和该环进行 换位,对于每个环求出这两个的最小值加起来就可以了.  .ed .cnj dgeonlineproblem?3270 # pk 1026 cipher  先找出所有置换循环,然后对于每一位来计算k% 循环长度后对应于哪个位置,o(n) 复杂度.注意读写方面的东西.  .ed .cnj dgeonlineproblem?1026 * 置换幂运算: # pk 1721 cards  详细见05 集训队论文"置换群快速幂运算研究与探讨".  dgeonlineproblem?1721 # pk 3128 leonardo s notebook 摘自: .aspx 题目意思是:一个置换是否可以由另一个置换的平方得来的.一个置换的平方,原来偶数长的循环会被分裂成两段长度相等的循环,而奇数长的循环不会被分裂.题 目只是问是否存在,所以只要看所给置换中偶数长的循环是否成对,否则就不能由一个置换的平方得来. 补充:因为如果所给置换的循环是偶数,则肯定是由分裂过来的,那么一定是成对的,否则如果是奇数,那么有可能是原来是奇数,也有可能是原来的偶数分裂成两 个奇数循环.  dgeonlineproblem?3128 * 推荐:(不错的应用) # pk 3590 the sh ffle problem  把n 分解成若干个数,使得他们的lcm 最大.在所取的数都是素数幂的时候是最大的,所以可以用递归来枚举所有的分解情况,而且由于要输出序最小的, 所以对于剩下的数可以直接单独都作为一个循环,这样就可以使得序最小了.此外,这道题目需要注意求最大的lcm 的时候不能用dp 来做,因为这个具有后效 性,局部最优不一定使得全局最优.  dgeonlineproblem?3590 3. 素数,整数分解,欧拉函数 素数是可能数论里最永恒,最经典的问题了(我们的队名就叫primem sic^-^ ).素数的判断,筛法求素数,大素数的判断··· 还有很多其他问题 都会用到素数. * 最水最水的:(心情不爽时用来解闷吧) # pk 1365 prime land # pk 2034 anti-prime seq ences 直接搜索,用dl 优化会快很多. # pk 2739 s m of consec tive prime n mbers pk 3518 prime gap pk 3126 prime path pk 1595 prime c ts pk 3641 pse doprime n mbers pk 2191 mersenne composite n mbers pk 1730 perfect pth powers pk 2262 goldbach s conject re pk 2909 goldbach s conject re * 筛法: # pk 2689 prime distance (很好的一个应用) 先找出sqrt(2^32) 内的所有素数,然后类似筛选法筛选掉[l, ]范围内的数  dgeonlineproblem?2689 * 反素数: # zoj2562 more divisors waing... 后记:素数表少打了一个19 ~晕死啊~..  .ed .cnonlinej dgeshowproblem.do?problemcode=2562 * 素数判断,整数分解: 这两题都要用到miller_rabin 的素数判断和pollard_rho 的整数分解,算法书上都会有,应该是属于模板题吧,不过最好看懂自己敲一 遍. # pk 1811 prime test  学习miller 和pollard 的题目.  .ed .cnj dgeonlineproblem?1811 # pk 2429 gcd & lcm inverse  分解lcmgcd 为互质的p,q ,要用到miller rabin 和pollard rho 算法,基本上做出来之后都是模板题了.  .ed .cnj dgeonlineproblem?2429 * 欧拉函数: 数论里很多地方都能用到欧拉函数,很重要的. # pk 1284 primitive roots (很水) 定理:对于奇素数m, 原根个数为phi(phi(m)), 由于phi(m)=m-1, 所以为phi(m-1)  .ed .cnj dgeonlineproblem?1284 # pk 2407 relatives (很水)  .ed .cnj dgeonlineproblem?2407 # pk 2773 happy 2006 n 之后的互质的数都是n 之前的加上n 的倍数的.  dgeonlineproblem?2773 # pk 2478 farey seq ence (快速求欧拉函数) 求前n 个欧拉函数的和,用学习指导里面的n*(1+lnln(n)) 的算法就可以了,非常快.  dgeonlineproblem?2478 # pk 3090 visible lattice points (法雷级数)  .ed .cnj dgeonlineproblem?3090 * 推荐:(欧拉函数,费马小定理) # pk 3358 period of an infinite binary expansion 转化为高次同余方程.  .ed .cnj dgeonlineproblem?3358 * 整数分解 这个也很重要的耶,包括大数的表示方法. # pk 2992 divisors 注意预处理,有很多组数据.  .ed .cnj dgeonlineproblem?2992 ? fz 1753 another easy problem 记得n! 有多少个p 的幂是怎么求的.  .ed .cnproblem.php?p1753 hit2813 garden visiting   dgeshow.php?pro2813 ? pk 3101 astronomy (分数的最小公倍数) 高精度gcd ,超时中.  .ed .cnj dgeonlineproblem?3101 4. 扩展欧几里得,线性同余,中国剩余定理 这应该是数论里比较重要的一个部分吧,这类的题目也挺多,具体的内容最好先看看数论书,我也整理过一些,可以参考参考:  .com с _shwblogitem0d56a87d4afbf2c093l * 简单题: # pk 1006 biorhythms  注意最后结果为0 或负数的情况  .ed .cnj dgeonlineproblem?1006 # pk 1061 青蛙的约会  .ed .cnj dgeonlineproblem?1061 # pk 2891 strange way to express integers x==a1(mod m1),x==a2(mod m2), 两个方程可以求出x ,然后重新令a1 为求出的解x,m1=lcm(m1,m2) ,然后继续和后面的进行求解.注意数据运算过程中可能溢出的问题.  .ed .cnj dgeonlineproblem?2891 # pk 2115 c looooops  .ed .cnj dgeonlineproblem?2115 # pk 2142 the balance  枚举,x=x0+bd*t ,直到xmin(x+y)  dgeonlineproblem?2142 * 强烈推荐: # sg 106 the eq ation  求ax+by=c 的时候,考虑a,b 为零的特殊情况,此外,若a,b 不是非负数,那么扩展欧几里德会有问题,于是我们可以把求x,y 变为求 x =-x,y =-y ,此时a,b, 就可以变为非负数来处理,同时x ,y 的范围也要相应取反.而且在取得区间时候,要注意区间边缘要进行相应的取 整.后记:要用cin,co t 才能ac ,用printf 会wa ...极度无奈中,偶然才发现的~_ ~!  .r problem.php?contest=0&problem=106 # pk 3708 rec rrent f nction (经典) 具体数学第一章.对于每一位求出循环节m1 ,还有该位从m 达到k最少要经过r1 次标号变化,于是就可以得到x==r1 (mod m1) ,然后同样的方法求其他的位,接着就可以两两方程这样解中国剩余定理.  .ed .cnj dgeonlineproblem?3708 5. 约瑟夫环问题 这个问题还是比较有意思的,不是很难. * 简单题: # pk 3517 and then there was one  .ed .cnj dgeonlineproblem?3517 # pk 1781 in danger  .ed .cnj dgeonlineproblem?1781 # pk 1012 joseph  考虑剩下k+1 个人,那么上一个出局的人肯定是坏人,所以考虑接下来一定要最后一个坏人出局,所以m==0 或1(mod k+1) .然后枚举m ,再验证.  dgeonlineproblem?1012 # pk 2244 eeny meeny moo  dgeonlineproblem?2244 * 推荐: # pk 2886 who gets the most candies? 线段树+ 反素数.  dgeonlineproblem?2886 6. 高斯消元法解方程 其实解方程并不是很难,就是按线性代数中学的那种方法,把系数矩阵化成上三角矩阵或数量矩阵,不过有些题目要判断是否有解,或枚举所有解.不过这类题目 我认为比较难的还是怎么去建立这个方程组,这个理解了,就没什么大问题了. * 简单题: # pk 1222 extended lights out  解异或运算的方程.n*m 个方程和未知数.  dgeonlineproblem?1222 # pk 1681 painter s problem  dgeonlineproblem?1681 # pk 1830 开关问题  以上三题做法都一样.  dgeonlineproblem?1830 * 推荐: # pk 2947 widget factory  最好要化成严格的阶梯型,方便判解.而且模某个数的时候解方程要用到扩展欧几里德算法.  dgeonlineproblem?2947 # pk 2065 seti 与上题一样.  dgeonlineproblem?2065 * 强烈推荐: # pk 1753 flip game  数据范围比较小,枚举可过.如果用高斯消元做,那么对于多解的时候也是需要枚举的,而且这种类型不具有太大的扩展性,这里高斯消元不见的比枚举要优 越.  dgeonlineproblem?1753 # pk 3185 the water bowls  同样如果对于无数解的时候,就需要对解进行枚举.其实这道题目可以先枚举第一位是否需要翻转,然后其他的就已经确定了,不过需要注意如果第一位翻转的 时候,答案别忘了加上去,我因为这个搞了好久~~~郁闷.  dgeonlineproblem?3185  同类题目,我自己加上去的. pk 1395 pk 2055 ral1561 pk 3254 * 变态题: pk 1487 single-player games  dgeonlineproblem?1487 7. 矩阵 用矩阵来解决问题确实很常见,但我现在用到还不是很好,很多难题我还不会做.建议大家可以去看matrix67的那篇关于矩阵的十个问题,确实很经典, 但不太好看懂. * 简单: pk 3070 fibonacci  dgeonlineproblem?3070 pk 3233 matrix power series  dgeonlineproblem?3233 pk 3735 training little cats  dgeonlineproblem?3735 8. 高次同余方程 有关这个问题我应该是没什么发言权了,a^b%c=d ,我现在只会求d 和b ,唉,很想知道a 该怎么求.就先推荐几道题目吧,这里涉及到了一个baby- step ,giant-step 算法. # fz 1759 s per a^b mod c a^b%c=a^(b%phi(c))%c , 注意a==c 的情况,  .ed .cnproblem.php?p1759 # pk 3243 clever y  和上面差不多,不过c 不一定是素数,所以方法就是解出a^m*x+c*y=gcd(a^m,c) 的所有解来判断,若无解则不管,因为c 不是素数可能 a^m 没有逆.  dgeonlineproblem?3243 # pk 2417 discrete logging hash ,最直接的离散对数  dgeonlineproblem?2417 ? hd 2815 mod tree  超时中,时限好像挺紧的.  .ed .cnshowproblem.php?p2815 # sg 261 求a wa test 23.. 后记:原来是hash 有错误,因为用了vector 后是从0 开始的,而我判断hash 链表结束的是0 ,如果恰好最后一个是在vector 的0 位 置,那么就会忽略掉这个数据,所以就会出现找不到那个数的情况.另外进行最后答案输出的时候,vector 的size 是返回 nsigned int 的,如果size( )是0 ,那么size-1就是2^32-1 了,所以这里就需要特别注意. ?  .ed .cnonlinej dgeshowproblem.do?problem3538 handling... 还没有找出更好的方法解决当a 和p 不互质情况下的解法.  9. 容斥原理,鸽巢原理 很有用的两个定理,但好像单独考这两个定理的不是很多. * 鸽巢原理: # pk 2356 find a m ltiple  同下.  dgeonlineproblem?2356 # pk 3370 halloween treatsn 个数,寻找c 个(c=n) ,使得他们的和为c 的倍数.由抽屉原理,前n 个数的mod c 肯定有重复的,那么一定存在一个区间使得他们的和是c 的倍数.  dgeonlineproblem?3370 * 容斥原理: # hd 1695 gcd  求gcd(x,y)=k 的个数,相当于求gcd(xk,yk)=1 的个数,其中xk 在[ak,bk],yk 在[ck,dk] 之间.所 以就是求在一定区间内,x ,y 互质的对数.假设b (此处b,d 已除k )那么对于=b, 直接用欧拉函数就可以了,对于[b+1,d] 之 间的数,对于每一个分解质因数,然后利用容斥原理,求出[1,b ]之间和这个数互质的个数.注意最后答案可能超过int ,用i64d 输出.  .ed .cnshowproblem.php?p1695 # hd 2461 rectangles  对称情况下才能使用懒标记,而且覆盖的标号不向下传.另外在pk 3695 上同样的题目由于时限很紧,所以可以对坐标进行离散化.log1000 和 log40 还是有差别的.  .ed .cnshowproblem.php?p2461 10. 找规律,推公式 这类题目的设计一般都非常巧妙,真的是很难想出来,但只要找到规律或推出公式,就不是很难了.我很多都是在参考别人思路的情况下做的,能自己想出来真的 很不容易. * 个人感觉都挺不错的: # pk 3372 candy distrib tion 找规律...其实可以进行分析的.  dgeonlineproblem?3372 # pk 3244 difference between triplets 这道题目要用到一个很巧妙的转化,把比较转化为绝对值的计算.因为max(a,b,c)-min(a,b,c)=(|a- b|+|a-c|+|b-c|)2, 然后剩下的就容易做了.  dgeonlineproblem?3244 pk 1809 regetni  dgeonlineproblem?1809 pk 1831 不定方程组  dgeonlineproblem?1831 # pk 1737 connected graph f[n] 为n 个点的联通数,那么f[n]=2^(c[n][2])-sigma(f[k]*c[i-1][k-1]*2^(c[n-k][2]))  dgeonlineproblem?1737 # pk 2480 longge s problemsigma(gcd(i,n))=sigma(d|n && d*[gcd(i,n)==d]), 枚举所有n 的约数d ,然后对于nd ,找出所有和nd 互质的数的个数就是gcd(i,n)==d 的个数,从而用欧拉 函数解决.  dgeonlineproblem?2480 pk 1792 hexagonal ro tes  .ed .cnj dgeonlineproblem?1792 11. 排列组合,区间计数,计数序列 这些题目可能需要一些组合数学知识,基本上高中的知识就够了.区间计数问题一般不难,但写的时候需要仔细一些,各种情况要考虑到位.至于像卡特兰数,差 分序列,斯特灵数··· 都还挺有意思,可以去看看"组合数学". * 简单题: pk 1850 code  dgeonlineproblem?1850 pk 1150 the last non-zero digit  dgeonlineproblem?1150 pk 1715 hexadecimal n mbers  dgeonlineproblem?1715 pk 2282 the co nting problem  dgeonlineproblem?2282 pk 3286 how many 0 s?  dgeonlineproblem?3286 * 推荐: pk 3252 ro nd n mbers  dgeonlineproblem?3252 * 计数序列: pk 1430 binary stirling n mbers  dgeonlineproblem?1430 pk 2515 birthday cake  .ed .cnj dgeonlineproblem?2515 pk 1707 s m of powers  .ed .cnj dgeonlineproblem?1707 12. 二分法 二分的思想还是很重要的,这里就简单推荐几个纯粹的二分题. * 简单: pk 3273 monthly expense  dgeonlineproblem?3273 pk 3258 river hopscotch  dgeonlineproblem?3258 pk 1905 expanding rods  dgeonlineproblem?1905 pk 3122 pie  dgeonlineproblem?3122 * 推荐: # pk 1845 s mdiv  令a=p1^m1 * p2^m2 * ... * pk^mk, 那么由于因数和是一个积性函数, 所以 f(a)=f(p1^m1)*f(p2^m2)*.. ; f(x^t)=1+x+x^2+..+x^t=(1-x^(t+1))(1-x); 由于mod 某个数,所以可以1(1-x) 可以用同余数解决.不过注意如果mod | x-1, 那么 f(x^t)=t+1 特殊处理一下.  .ed .cnj dgeonlineproblem?1845 13. 稳定婚姻问题 无意中接触到这个算法,还蛮有意思的,"组合数学"中有详细的介绍. pk 3487 the stable marriage problem  .ed .cnj dgeonlineproblem?3487 zoj1576 marriage is stable  .ed .cnonlinej dgeshowproblem.do?problemcode=1576 14. 数位类统计问题 在航点月赛中第一次接触到这类问题,sca 大牛little 龙推荐我看了一篇论文,09 年刘聪的"浅谈数位类统计问题",这篇论文相当精彩,也相当详 细,每道题都有详细的分析和作者的参考代码.所以我也没什么可说的了,这些题的代码我博客里也就不贴了,大家直接去看论文吧. 简单: ral1057 amo nt of degrees  s.r problem.aspx?space=1&n m=1057 spoj1182 sorted bit sq ence  hd 3271 snibb  .ed .cnshowproblem.php?p3271 较难: spoj2319 seq ence  sg 390 tickets  .r problem.php?contest=0&problem=390 以上分类的题目在我的博客里都可以找到详细的解题报告和参考代码,由于比较麻烦就没加链接,需要的可以用我的站内搜索找到. 本小结会不断更新,转载请注明出处. 欧拉函数. # pk 3696 the l ckiest n mber (10^n-1+..+10+1)=(10^n-1)9, 欧拉函数,离散对数,注意溢出处理(相乘时变为at+b ).  .ed .cnj dgeonlineproblem?3696 树状数组 # hd 3333 先求出每个位置后面和它一样的最近的那个数的位置next[i] ,然后用树状数组记录不重复的前n 个数的和,接着对询 问区间排序,从左到右做,记left 为在当前区间左边的那些数,通过树状数组,将left 到next[left]-1 之间的所有的数都减去 val[left] ,然后就可以直接像s m[i]-s m[j] 那样方便的求出区间里面没有重复的数的和.  .ed .cnshowproblem.php?p3333 # pk 3222  树的dfs 和分治思想 解题报告见此: .ed .cnj dgeonline showmessage?