AC代码

 https://codeforces.com/contest/317/submission/181838688

题意：

 Vasya 和 Petya玩一个游戏，每人每次写一个x∈[1,n] 的正整数。

 当x 被写后，x 及x 的任意正整数幂都不能被写，写不了数字的人输。

 例如，如果在第一个回合选择了数字9，那么以后就不能选择9或81，而仍然可以选择3或27。

 假设 Vasya为先手，问当两边都是最佳操作时，谁能获胜。

 题解：

 如果x不是任一y(<x) 的正整数次幂，则把所有x的正整数次幂的数归为一类记为Pow(x)，

 显然任意两类不交，那么问题变成若干相同的子问题.

 暴力打表求出SG(1)~SG(30). 注意任一类的规模不超过log2n ， 

因为 n≤1e9，且 2^30>1e9 ，所以 log2n＜30 。

 注意到如果x>sqrt(n)，那么Pow(x) 规模是1，SG值为1.

 故只需要求出所有x≤sqrt(n)的Pow(x) 的规模对应的SG值且异或 ，

 再统计一下所有x>sqrt(n)且不是任意y(<x)y(<x)的正整数次幂的数的个数，

 奇数就对答案再异或1(SG(1)=1 )。