不可表达的数 --- 梅森数 庞果题目
本题的奖品由亿阳信通赞助，以下是题目详情给定表达式[x/2] + y + x * y, 其中x,y都是正整数。其中的中括号表示下取整，例如[3/2] = 1 ， [5/2] = 2。有些正整数可以用上述表达式表达出来，例如正整数2，当取x = y = 1时，可以把2表达出来 （ 解释下：当x=y=1时， [x / 2] + y + x * y = [1 / 2] + 1 + 1 * 1 = 0+1+1 = 2 ）；有些数可以有多种方式表达，例如13可以由 x = 2 y = 4 以及x = 3 y = 3来表示；有些数无法用这个表达式表达出来，比如3。从1开始第n个不能用这个表达式表示出来的数，我们叫做an，例如a1=1 a2=3,给定n，求an。输入：n值 1<=n<=40输出：an % 1000000007的结果（因为结果较大，输出an %1000000007的结果）。这个题目，开始的时候按照递推方法，我想找出一个通式，然后看有什么规律，来解这个题目。 由于有个[x/2]取整的操作，所以按照x为奇数和x为偶数来看。如果x为奇数，我们可以把表达式演算成(x+1)(2y+1)/2-1如果x为偶数，我们可以把表达式演算成(x+1)(2y+1)/2-1/2当x为奇数时，是1，3，5，7....对应的每个x，变量y可以任意取值1，2，3，4....所以对于第一个表达式：x=1时，表达式为2*(2y+1)/2-1=2y+1-1=2y，表示全体偶数,为了不和y混淆，我们用n来表示通式。用同样的方法，可以求得x为3，5，7，9....时，表达式分别为：4n+1,6n+2,8n+3....好像有点规律了。。。当x为偶数时，按照上面的办法，也可以写出表达式：3n+4,5n+7,7n+10,9n+13...这也好像有点规律了。。。对于每个表达式中n的取值都是1,2,3,4....但是有这个好像还不够，但是我实在是推不下去了，只能一个一个验证了，从3开始，看是否满足2n,4n+1,6n+2,8n+3.....3n+4,5n+7,7n+10,9n+13.......这些表达式,如果满足，那这个数是可表达的，如果不满足，就不可表达了。由于有2n，所以偶数不用去验证了，肯定满足，那么从3开始，我们挨个验证所有奇数，验证的时候也不用验证所有通式，比如5，只需要验证4n+1就行了，因为其他的表达式都比5要大。这样验证一趟下来，时间上肯定大于题目要求的运算时间3秒了，，在我能等待的时间内，我验证出了以下几个数满足要求：3，7，31，127，8191，131071 ....接着往下走就要算很久了，但是，作为搞计算机的我，看到31,127,8191这三个数，觉得特别熟悉，因为我们经常看到32，128，8192这几个数，这都是2的幂减1，再看看前面的3，7，也满足条件，后面的131071验证一下，也是2的幂减1，他们的幂分别是：2，3，5，7，13，17第一反应，是素数幂减1，但是没有11啊，擦，真悲剧，但是我实在是想不到了，于是把程序修改了一下，只验证素数次幂减1的情况，速度快了不少，多验证了两个出来（524287，2147483647），然后没管，就把程序提交了，结果必然是没通过超时了，但是至少前面几个应该是对的。后来闲着没事，我把2,3,5,7,13,17这几个在google上随便搜索了一下，发现一个keyword叫 MERSENNE的，中文叫梅森数,打开wiki百科的梅森数，呃。。。原来验证出来的数，个个都是梅森数啊。。下面有张表，是到目前为止发现的梅森数，前面几个和我验证的都一样，后面的那么大。。。擦，怪不得怎么算都不出结果。我怒了，直接把程序改了，先用python把前40个梅森数对1000007取模的结果算好（因为python直接支持大数运算），然后全加到一个数组中，题目输入多少，老子直接输出梅森数取模结果，秒杀啊，结果一提交，我擦，通过了。。。看来正确答案就是前40个梅森数啊。这是我做这道题的推导过程，在我看来，这已经变成一个纯数学问题了，而且至于为什么梅森数不可表示，我也不知道，只是最后发现了是这样的结果，这题目肯定还有其他我能理解的计算机算法，但是尼玛到目前为止，最快的计算机也才找出了48个梅森数，这题目要在3秒内找出40个，这不是坑爹吗？？？至少我不知道怎么搞。程序就不贴了，只有几行。。输入什么，直接输出对应的梅森数取模10000007。
补充：综合编程 , 其他综合 ,
