AC代碼

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

題意：

?Vasya 和 Petya玩一個(gè)游戲，每人每次寫一個(gè)x∈[1,n] 的正整數(shù)。

?當(dāng)x 被寫后，x 及x 的任意正整數(shù)冪都不能被寫，寫不了數(shù)字的人輸。

?例如，如果在第一個(gè)回合選擇了數(shù)字9，那么以后就不能選擇9或81，而仍然可以選擇3或27。

?假設(shè) Vasya為先手，問當(dāng)兩邊都是最佳操作時(shí)，誰能獲勝。

?

?題解：

?如果x不是任一y(<x) 的正整數(shù)次冪，則把所有x的正整數(shù)次冪的數(shù)歸為一類記為Pow(x)，

?顯然任意兩類不交，那么問題變成若干相同的子問題.

?暴力打表求出SG(1)~SG(30). 注意任一類的規(guī)模不超過log2n ，?

因?yàn)?n≤1e9，且 2^30>1e9 ，所以 log2n＜30 。

?

?注意到如果x>sqrt(n)，那么Pow(x) 規(guī)模是1，SG值為1.

?故只需要求出所有x≤sqrt(n)的Pow(x) 的規(guī)模對(duì)應(yīng)的SG值且異或 ，

?再統(tǒng)計(jì)一下所有x>sqrt(n)且不是任意y(<x)y(<x)的正整數(shù)次冪的數(shù)的個(gè)數(shù)，

?奇數(shù)就對(duì)答案再異或1(SG(1)=1 )。