@description@
有一个长度为N的数组，甲乙两人在上面进行这样一个游戏：
首先，数组上有一些格子是白的，有一些是黑的。然后两人轮流进行操作。每次操作选择一个白色的格子，假设它的下标为x。接着，选择一个大小在1~n/x之间的整数k，然后将下标为x、2x、...、kx的格子都进行颜色翻转。不能操作的人输。
现在甲（先手）有一些询问。每次他会给你一个数组的初始状态，你要求出对于这种初始状态他是否有必胜策略。
@solution@
考虑一个巧妙（至少我觉得很巧妙）的转化：我们把白色格子看作初始有一个棋子，颜色翻转变成直接在格子上放棋子。
当一个格子有多于 1 个棋子存在时，先手对该格子操作，后手可以模仿相同的操作。因此并不影响。
这样子转化的好处是：我们把每个白格子独立出来，变成互不干涉的组合游戏。因此就可以使用 sg 函数来刻画了。
可以列出转移 \(sg(x) = mex(0, sg(2x), sg(2x)\oplus sg(3x), \dots)\)。
然而 n 很大，考虑怎么优化。
注意当 x > n/2 时 sg(x) 相同，继续算发现 n/2 >= x > n/3 时 sg(x) 也相同，因此不难猜测到 \(sg(x) = f(\lfloor\frac{n}{x}\rfloor)\)。证明根据 sg 的转移式易证。
由 \(sg(x) = mex(0, sg(2x), sg(2x)\oplus sg(3x), \dots)\) 可得 f 的转移：
f(p) = mex(0, f(\lfloor\frac{p}{2}\rfloor), f(\lfloor\frac{p}{2}\rfloor)\oplus f(\lfloor\frac{p}{3}\rfloor), \dots)
\]
分块转移即可。存储 f 用类似杜教筛的方法即可。
时间复杂度 \(\sum_{i=1}^{\sqrt{n}}(\sqrt{\frac{n}{i}} + \sqrt{i})\)。积分拟合一下大概是 \(O(n^{\frac{3}{4}})\)。
@accepted code@
#include <cmath>
#include <cstdio>
#include <algorithm>
using namespace std;
const int SQRT = 32000;
int N; int sg1[SQRT + 5], sg2[SQRT + 5];
int *sg(int x) {return x > SQRT ? sg1 + (N/x) : sg2 + x;}
int a[2*SQRT + 5], vis[2*SQRT + 5], cnt;
void get() {
for(int i=1;i<=N;i=(N/(N/i))+1) a[++cnt] = N/i;
for(int i=cnt;i>=1;i--) {
int tmp = 0;
for(int j=2;j<=a[i];) {
int p = a[i] / j, k = a[i] / p, x = (*sg(p)) ^ tmp;
vis[x] = i;
if( (k - j + 1) & 1 )
tmp = x;
j = k + 1;
}
int ans = 1;
while( vis[ans] == i ) ans++;
(*sg(a[i])) = ans;
}
}
int main() {
scanf("%d", &N), get();
int K; scanf("%d", &K);
for(int i=1;i<=K;i++) {
int W, ans = 0; scanf("%d", &W);
for(int j=1;j<=W;j++) {
int x; scanf("%d", &x);
ans ^= (*sg(N/x));
}
puts(ans ? "Yes" : "No");
}
}
@details@
能少用除法就少用除法，毕竟最慢运算符（好像不是，取模是最慢的），很可能（像我一样）被卡常。