Home > Database > Mysql Tutorial > body text

SRM565 DIV1 LEVEL2 TheDivisionGame

WBOY
Release: 2016-06-07 15:38:46
Original
1232 people have browsed it

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;
				}
			}
		}
Copy after login



Related labels:
source:php.cn
Statement of this Website
The content of this article is voluntarily contributed by netizens, and the copyright belongs to the original author. This site does not assume corresponding legal responsibility. If you find any content suspected of plagiarism or infringement, please contact admin@php.cn
Popular Tutorials
More>
Latest Downloads
More>
Web Effects
Website Source Code
Website Materials
Front End Template