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




比如其中的一个素数2，从大于等于L的第一个2的倍数开始计算，计算每一个数有多少个2的因子。因为j += temp,所以我们每次去查找的话，都是有效的，及每一个j都是temp的倍数，这样就比我上面一个一个素数尝试过去快很多。


这样求好之后，后面就是一个简单的dp了，因为数字1001000000 

下面是代码：

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;
				}
			}
		}