SRM565DIV1LEVEL2TheDivisionGame

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<=R ; i++) {
	b[i - L] = i;
	} 
	memset(a , 0 , sizeof(a));

	for (int i=0 ; i

这样求好之后，后面就是一个简单的dp了，因为数字1001000000 < 2 ^ 31，每一个数最多也只有31个因子。ans[2][32], if (ans[u][j] != 0) ans[p][j ^ a[i - L] ] += ans[u][j]。然后我们统计全部不为and[u][j]且j不为的值就可以了。

下面是代码：

public:
 long long countWinningIntervals(int L, int R)
 {
	initPrime(((int)(sqrt(R * 1.0))) + 1); //attention!!!
	LL ret = 0;
 for (int i=L ; i<=R ; i++) {
	b[i - L] = i;
	} 
	memset(a , 0 , sizeof(a));

	for (int i=0 ; i n) break;
	gash[temp] = true;
	if (i % primes[j] == 0) break;
	}
	}
	}