记录编号	161146	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]数组游戏	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	1.912 s
提交时间	2015-05-01 20:59:37	内存使用	1.16 MiB

#include<cstdio>
#include<algorithm>
using namespace std;
const int L_N=70000;
int ni[L_N],sg[L_N],nn;
int nxt[L_N];
bool vis[L_N];
int N;
int main(){

	freopen("haoi2015_t3.in","r",stdin);
	freopen("haoi2015_t3.out","w",stdout);
	scanf("%d",&N);
	for(int i=1;i<=N;i=N/(N/i)+1){
		ni[++nn]=N/i;
		//printf("%d\n",N/i);
	}
	reverse(ni+1,ni+1+nn);
	for(int k=1;k<=nn;k++){
		int n=ni[k];
		int mx=0,now=0; vis[0]=true;
		int p=k-1, st=2;
		while(st<=n){
			int nst=n/st;
			while(nst<ni[p]) p--;
			p=nxt[p];
			int ed=n/ni[p];
			
			int tmp=now^sg[p];
			mx=max(tmp,mx);
			vis[tmp]=true;
			
			if((ed-st+1)&1) now^=sg[p];
			
			st=ed+1;
		}
		
		bool ok=false;
		for(int i=0;i<=mx+1;i++){
			if(!ok && !vis[i]) sg[k]=i, ok=true;
			vis[i]=false;
		}
		if(sg[k]==sg[k-1]) nxt[k]=nxt[k-1];
		else nxt[k]=k;
		
		//printf("n=%d sg=%d\n",n,sg[k]);
	}

	int T; scanf("%d",&T);
	for(int t=1;t<=T;t++){
		int n;scanf("%d",&n);
		int s=0;
		for(int i=1;i<=n;i++){
			int x;scanf("%d",&x);
			x=N/x;
			x=lower_bound(ni+1,ni+1+nn,x)-ni;
			s^=sg[x];
		}
		printf(s?"Yes\n":"No\n");
	}
	return 0;
}