Maison >base de données >tutoriel mysql >SRM565 DIV1 LEVEL2 TheDivisionGame
http://community.topcoder.com/stat?c=problem_statementpm=12264 这道题目的意思就是有一堆数字,每次操作可以这样做,从中选出一个大于1的数字a,然后使用这个数任意一个大于1的因子b去除以这个数,及 a / b,然后使用结果来替换a。这样两个人轮流操作,
http://community.topcoder.com/stat?c=problem_statement&pm=12264
这道题目的意思就是有一堆数字,每次操作可以这样做,从中选出一个大于1的数字a,然后使用这个数任意一个大于1的因子b去除以这个数,及 a / b,然后使用结果来替换a。这样两个人轮流操作,谁不能操作了就算输了。
这题很有博弈的味道。如果对于博弈不熟悉的话,可以看看下面的这篇文章,写的很详细
http://blog.csdn.net/acm_cxlove/article/details/7854530
如果看了上面的那篇文章,文章中有提到这样的一种博弈,有n堆石子,每次操作我们可以拿其中一堆中的任意个,及可以拿一个,或者多个,或者一次都拿完。其实这个和我们这题很相似,对于我们挑选的一个数字,这个数字有多杀个质因子,就类似这堆石子有多少个。如12 = 2 * 2 * 3,有三个质因子,那么我们就能把这个数字看作是有3颗石子的堆。现在假设我们知道了每堆石子,及每个数有多少个质因子,那么我就能求求出答案了。现在我们就要求出从L到R,这几个数每一个数有多少个质因子。
1、首先筛选出sqrt(R) + 1中有哪些素数
2、计算每一个从L到R的数有多少个质因子。我刚开始的时候,是从L到R,每一个都数都单独的求。及对于其中的一个数a,我使用上面求好的素数数列一个一个验证过去是不是a的质因子,如果是的话有几个。但是这样求的话,效率很不好,超时了。后面我看了别人的答案,我看到了种更好的方法。我的这个朴素的方法中,我是一个一个素数验证过去的,所以有很多不是a的因子的,我也要验证一一下,这样就会浪费很多的效率。另外一个方法就是我们使用素数去主动的查看L到R中的数中有多少个这样的素数。看下面的代码会更加的清楚
for (int i=L ; i<br> <br> 比如其中的一个素数2,从大于等于L的第一个2的倍数开始计算,计算每一个数有多少个2的因子。因为j += temp,所以我们每次去查找的话,都是有效的,及每一个j都是temp的倍数,这样就比我上面一个一个素数尝试过去快很多。 <p>这样求好之后,后面就是一个简单的dp了,因为数字1001000000 </p><p>下面是代码:</p> <pre class="brush:php;toolbar:false">public: long long countWinningIntervals(int L, int R) { initPrime(((int)(sqrt(R * 1.0))) + 1); //attention!!! LL ret = 0; for (int i=L ; i n) break; gash[temp] = true; if (i % primes[j] == 0) break; } } }