本文目录
梅森素数的寻找历程
2300多年来，人类仅发现49个梅森素数，由于这种素数珍奇而迷人，因此被人们誉为 “数海明珠” 。自梅森提出其断言后，人们发现的已知最大素数几乎都是梅森素数，因此寻找新的梅森素数的历程也就几乎等同于寻找新的最大素数的历程。
梅森素数的探寻难度极大，它不仅需要高深的理论和纯熟的技巧，而且需要进行艰苦的计算。 在计算能力低下的公元前，人们仅知道四个2p－1型素数：3、7、31和127，发现人已无从考证。1456年，又一个没有留下姓名的人在其手稿中给出了第5个2p－1型素数：8191。而在梅森之前，意大利数学家卡塔尔迪（1548～1626）也对这种类型的素数进行了整理，他在1588年提出 和 也是素数，由此成为第一个在发现者榜单上留名的人。
手算笔录的时代，每前进一步，都显得格外艰难。1772年，在卡塔尔迪之后近200年，瑞士数学家欧拉（1707～1783）在双目失明的情况下，靠心算证明了 是一个素数。这是人们找到的第8个梅森素数，它共有10位数，堪称当时世界上已知的最大素数。欧拉还证明了欧几里得关于完全数定理的逆定理：所有的偶完全数都具有 2p－1（2p－1）的形式，其中2p－1是素数。这表明梅森素数和偶完全数是一一对应的。
100年后，法国数学家卢卡斯（1842～1891）提出了一个用来判别Mp是否为素数的重要定理——卢卡斯定理，为梅森素数的研究提供了有力的工具。1876年，卢卡斯证明 是素数，这是人们靠手工计算发现的最大梅森素数，长达39位。
1883年，俄国数学家波佛辛（1827～1900）利用卢卡斯定理证明了 也是素数——这是梅森漏掉的。梅森还漏掉另外两个素数： 和 ，它们分别在1911年与1914年被数学家鲍尔斯（1875～1952）发现。
卢卡斯第一个否定了 “M67为素数” 这一自梅森断言以来一直被人们相信的结论，但他未能找到其因子。直到1903年，才由数学家科尔（1861～1926）算出267－1=193707721×761838257287。1922年，数学家克莱契克（1882～1957）进一步验证了M257并不是素数，而是合数。
在手工计算的漫长年代里，人们历尽艰辛，一共只找到12个梅森素数。 20世纪30年代，美国数学家莱默（1905～1991）改进了卢卡斯的工作，给出了一个针对Mp的新的素性测试方法，即卢卡斯-莱默检验法：Mp》3是素数当且仅当Lp－2=0，其中L0=4，Ln+1=（Ln2 －2）modMp。这一方法在 “计算机时代” 发挥了重要作用。
1952年，美国数学家鲁滨逊（1911～1995）在莱默指导下将此方法编译成计算机程序，使用SWAC型计算机在几个月内，就找到了5个梅森素数： 、 、 、 和 。其后， 在1957年被黎塞尔（1929～ 2014）证明是素数； 和 在1961年被赫维兹（1937～ ）证明是素数。
1963年，美国数学家吉里斯（1928～1975）证明 和 是素数。
1963年6月2日晚上8点，第23个梅森素数 通过大型计算机被找到。发现这一素数的美国伊利诺伊大学数学系全体师生感到无比骄傲，以致于把所有从系里发出的信件都敲上了 “211213－1是个素数” 的邮戳。
超级计算机的引入加快了梅森素数的寻找步伐，但随着指数p值的增大，每一个梅森素数的产生反而更加艰难。1971年3月4日晚，塔克曼（1915～2002）使用IBM360-91型计算机找到新的梅森素数 。而到1978年10月，世界几乎所有的大新闻机构（包括中国的新华社）都报道了以下消息：两名年仅18岁的美国高中生诺尔（1960～ ）和尼科尔使用Cyber-174型计算机找到了第25个梅森素数 。
1979年2月，诺尔又独自发现第26个梅森素数 。
伴随数学理论的改善，为寻找梅森素数而使用的计算机也越来越强大，包括了著名的IBM360型计算机和超级计算机Cray系列。1979年4月，史洛温斯基使用Cray-1型计算机找到梅森素数 。使用经过改进的Cray-XMP型计算机在1982年至1985年间找到了3个梅森素数： 、 和 。但他未能确定M86243和M216091之间是否有异于M132049的梅森素数。
1988年，科尔魁特和韦尔什使用NEC-SX2型超高速并行计算机果然发现 。沉寂4年之后，哈威尔实验室（英国原子能技术权威机构）的一个研究小组宣布他们找到梅森素数 。
1994年1月10日，史洛温斯基和盖奇再次夺回发现已知最大素数的桂冠——这一素数是 。而下一个梅森素数 仍是他们的成果，史洛温斯基由于发现7个梅森素数，而被人们誉为 “素数大王” 。1996年发现的M1257787是迄今为止最后一个由超级计算机发现的梅森素数，数学家使用了Cray-T94，这也是人类发现的第34个梅森素数。 使用超级计算机寻找梅森素数实在太昂贵了，而且可以参与的人也有限，网格这一崭新技术的出现使梅森素数的搜寻又重新回到了 “人人参与” 的大众时代。20世纪90年代中后期，在美国程序设计师沃特曼和库尔沃斯基等人的共同努力下，建立了世界上第一个基于互联网的分布式计算项目——因特网梅森素数大搜索（GIMPS）。人们只要在GIMPS的主页上下载一个计算梅森素数的免费程序，就可以立即参加该项目来搜寻新的梅森素数。
1996年至1998年，GIMPS找到了3个梅森素数： 、 和 ，其发现者来自法国、英国和美国。
1999年6月1日，美国密歇根州普利茅茨的数学爱好者哈吉拉特瓦拉通过GIMPS项目找到第38个梅森素数 ，这是20世纪发现的最后一个梅森素数，也是人们知道的第一个超过100万位的素数。如果把它写下来的话，共有2098960位数字。
进入21世纪，随着个人计算机的进一步普及和计算速度的提升，人们又找到不少更大的梅森素数。加拿大志愿者卡梅伦在2001年11月找到 ，拉开了新世纪寻找梅森素数的序幕。 此后在2003年至2006年间，GIMPS又相继发现5个梅森素数： 、 、 、 和 ，最大素数纪录离1000万位大关越来越近。
2008年8月23日，美国加州大学洛杉矶分校的计算机专家史密斯终于发现超过1000万位的梅森素数 。 它有12978189位数，如果用普通字号将这个巨数连续打印下来，它的长度可超过50公里！这一成就被美国的《时代》杂志评为 “2008年度50项最佳发明” 之一，排名在第29位。
此后一年内，又有两个1000万位以上的梅森素数被德国和挪威的志愿者先后找出。 距史密斯的发现仅相隔两个星期，而2009年4月找到的 与史密斯发现的素数相比 “仅” 相差14万位数。
2013年1月，美国中央密苏里大学数学教授柯蒂斯·库珀领导的研究小组发现了第48个梅森素数 。 这一发现被英国《新科学家》周刊评为当年自然科学十大突破之一。 2016年1月7日，库珀又发现第49个梅森素数 274207281－1。这个超大素数有22338618位，是目前已知的最大素数。这已是库珀第四次通过GIMPS项目发现新的梅森素数。
梅森素数的大事记
公元前4世纪，古希腊数学家欧几里得在《几何原本》第九章中论述了完全数与2p－1型素数的关系，并提出有少量素数可表示成2p－1（p为素数）的形式，由此开创了研究2p－1型素数的先河。 15世纪，发现第5个2p－1型素数。 16世纪，意大利数学家卡塔尔迪开始对此类素数进行整理。 17世纪，法国数学家马林·梅森的工作成为2p－1型素数研究的转折点和里程碑之一，“梅森素数” 也由此得名。 18世纪，瑞士数学家欧拉证明了完全数定理的逆定理，并心算出第8个梅森素数M31，是当时已知的最大素数。 19世纪70年代，法国数学家卢卡斯提出了一个用来判别Mp是否为素数的重要定理——卢卡斯定理，并证明了M127是一个素数。卢卡斯的工作为梅森素数的研究提供了有力的工具。 19世纪末至20世纪初，数学家利用卢卡斯定理又陆续证明M61、M89、M107是素数。人类在 “手算笔录时代” 共发现12个梅森素数。 20世纪30年代，美国数学家莱默改进了卢卡斯的工作，给出了一个针对Mp的新的素性测试方法，即卢卡斯-莱默检验法。此方法在 “计算机时代” 发挥了重要作用，时至今日仍是检测梅森数素性的最佳方法。 电子计算机的发明革命化的改进了梅森素数的寻找，仅在1952年就找到5个梅森素数。此后为寻找梅森素数而使用的计算机功能也越来越强大。 1992年，中国学者周海中提出了一个关于梅森素数分布的猜想，并首次给出其分布的精确表达式。这一猜想在国际数学界引起较大反响，被命名为 “周氏猜测” 。 1996年，著名的 “因特网梅森素数大搜索”（GIMPS）项目建立，加快了寻找更大梅森素数的进程。 1999年3月，美国电子前沿基金会（EFF）向全世界宣布了为寻找更大的梅森素数而设立的奖金。至2008年8月，已发现超过1000万位的梅森素数。
什么是梅森素数为什么要探索梅森素数
梅森素数是由梅森数而来。所谓梅森数，是指形如2ⁿ-1的一类数，其中指数n是素数，常记为Mn ，如果梅森数是素数，就称为梅森素数。用因式分解法可以证明，若2ⁿ-1是素数，则指数n也是素数。
“梅森素数”（Mersenne prime）是指形如2^P-1的素数，如2^2-1=3、2^3-1=7、2^5-1=31等。早在2300年前,古希腊数学家欧几里得用反证法证明素数有无穷多个；他认为，其中一些素数可写成2^P-1的形式。
由于2^P-1型素数具有独特的性质和无穷的魅力，千百年来一直吸引着众多的数学家和无数的业余数学爱好者对它进行探究。17 世纪法国数学家马林·梅森是他们中最杰出的探究者。
由于梅森学识渊博、才华横溢、为人热情以及最早系统而深入地研究2^P-1型素数，为了纪念他，数学界将这种特殊形式的素数命名为“梅森素数”。迄今为止,人类仅发现51个梅森素数。这种素数珍奇而迷人,因而被人们称为“数学宝山上的钻石”。梅森素数历来是数论研究的一项重要内容,也是当今科学探索的热点和难点之一。
2^P-1貌似简单,但探究难度却很大；当指数P值较大时，不仅需要高深的理论和纯熟的技巧，而且还需要进行艰巨的计算。1772年,有“数学英雄”美名的瑞士数学大师莱昂哈德·欧拉在双目失明的情况下，靠心算证明了2^31-1(即2147483647)是第8个梅森素数。这个具有10位的素数，堪称当时世界上已知的最大素数。
在“手算笔录”的年代，人们历尽艰辛,仅找到12个梅森素数。而计算机的产生加速了梅森素数探究进程。1952年，美国数学家拉斐尔·鲁滨逊等人使用SWAC型计算机在短短的几个月内，就找到了5个梅森素数：2^521-1、2^607-1、2^1279-1、2^2203-1和2^2281-1。
探索梅森素数的原因
它促进了分布式计算技术的发展。从最新的17个梅森素数是在因特网项目中发现这一事实，可以想象到网络的威力。分布式计算技术使得用大量个人计算机去做本来要用超级计算机才能完成的项目成为可能，这是一个前景非常广阔的领域，它的探究还推动了快速傅立叶变换的应用。
梅森素数在实用领域也有用武之地，现在人们已将大素数用于现代密码设计领域。其原理是：将一个很大的数分解成若干素数的乘积非常困难，但将几个素数相乘却相对容易得多，在这种密码设计中，需要使用较大的素数，素数越大，密码被破译的可能性就越小。
TopCoder SRM 泛做一（548 ~ 599）
记录大部分Hard题，和部分难度较大的Medium
548C 容斥原理，分类计数 注意到 特别小，可以分类讨论。需要解决一个弱化的问题： 个点 条边的连通图个数，通过经典的容斥解决。以 为例，首先按照 是否连接分类（若连接可以转化为 的情况）。否则接下来按照删除 后的连通块个数讨论即可。
549B 博弈，状压DP 注意到帽子的数量特别少，于是可以状压。 分别表示是否翻开以及是否有硬币。可以预处理所有的合法状态。注意到 DP 的状态值只需要记录收集到的硬币个数即可。
550B 杨辉三角，卢卡斯定理推论 首先得到一些性质：每次放置的检验器 均相同，且刚好加 ， 的一定被 整除，而 的被 除余 。注意到 ，下标变换为 ，即是模 意义下的杨辉三角。利用经典的卢卡斯定理推论： 。
550C 矩阵快速幂 注意到使每个位置变为相同的总变换次数 （以及总代价 ）是固定的，之后根据 我们可以求出 表示最多多余的周期。 表示当前还差 次， 次变化的位置个数，转移 次即可。容易发现不会重复计数，或者出现不合法的情况。
551C Meet-in-the-middle，矩阵树定理，容斥 分解问题，不妨枚举恰有 个真甜水果，于是要解决：1.选取 个甜水果，且其甜度不超过 ， 解决。2.有 个真甜水果，求生成树个数，矩阵树定理+容斥（注意到容易求出“至多”有..个方案）
552C DP，trick 直接令 表示 中的质数之于 的答案，枚举 的选择个数即可。然而只需注意到，当 时， 至多只有一个质因子，二分质数表即可。复杂度比较玄学...
564C DP，异或性质 考虑到：如果存在一个 位变量没有任何限制，那么异或和的结果是等概率的。于是枚举第一次存在一个限制的位置，根据 这一位的奇偶性，DP 即可
