记录编号	162028	评测结果	AAAAAAAAAA
题目名称	[HAOI 2015]数组游戏	最终得分	100
用户昵称	Asm.Def	是否通过	通过
代码语言	C++	运行时间	1.172 s
提交时间	2015-05-13 12:22:07	内存使用	24.23 MiB

/*****************************************************************************/
/******************************Designed By Asm.Def****************************/
/*****************************************************************************/
#include <cstring>
#include <cstdio>
#include <algorithm>
#include <cstdlib>
#include <cctype>
#include <ctime>
#define SetFile(x) (freopen(#x".in", "r", stdin), freopen(#x".out", "w", stdout) )
//#define FREAD
#define FREADLENTH 5000000
#ifdef FREAD
char *fread_ptr = (char*)malloc(FREADLENTH);
#define getc() (*(fread_ptr++))
#else
#define getc() getchar()
#endif
using namespace std;
template<class T>inline void getd(T &x){
	int ch = getc();bool neg = false;
	while(!isdigit(ch) && ch != '-')ch = getc();
	if(ch == '-')neg = true, ch = getc();
	x = ch - '0';
	while(isdigit(ch = getc()))x = x * 10 - '0' + ch;
	if(neg)x = -x;
}
/*******************************************************************************/
const int maxn = 64000, P = 2000003;
int N, val[maxn], vcnt, vt[maxn], checklist[maxn];
bool check[maxn];
int SG[maxn];
#include <vector>
 
vector<int> Hash[P];
typedef vector<int>::iterator iterator;
 
inline int find(const int *L, size_t len, int x){
	const int *R = L + len - 1, *mid;
	while(L <= R){
		mid = L + (R-L) / 2;
		if(val[*mid] > x)L = mid + 1;
		else R = mid - 1;
	}
	return *L;
}
 
inline int ind(int x){
	vector<int> &v = Hash[x % P];
	return find(&v[0], v.size(), x);
}
 
inline void init(){
	getd(N);
	int i, j, t, s, vtcnt, c, tmp;
	int ccnt;//回滚check数组
	for(i = 1;i * i <= N;++i)val[vcnt++] = i;
	for(j = N / i;j;--j)val[vcnt++] = N / j;
	for(i = 0;i < vcnt;++i){
		t = val[i];s = ccnt = vtcnt = 0;
		for(j = 1;j * j <= t;++j)vt[vtcnt++] = j;
		for(j = t / j;j;--j)vt[vtcnt++] = t / j;//vt:乘k之后能出现的长度
		for(j = vtcnt-2;j >= 0;--j){
			//printf("ind(%d) = %d\n", vt[j], ind(vt[j]));
			tmp = SG[ind(vt[j])];
			c = t / vt[j] - t / (vt[j] + 1);//出现次数
			check[checklist[ccnt++] = s ^ tmp] = true;
			if(c & 1)s ^= tmp;
		}
		j = 1;while(check[j])++j;
		SG[i] = j;
		Hash[t % P].push_back(i);
		for(j = 0;j < ccnt;++j)check[checklist[j]] = false;
	}
}
 
inline void work(){
	int K, qcnt, sum, t;
	getd(K);while(K--){
		getd(qcnt);
		sum = 0;
		while(qcnt--){
			getd(t);
			sum ^= SG[ind(N / t)];
		}
		if(sum)puts("Yes");
		else puts("No");
	}
}
 
int main(){
 
#ifdef DEBUG
	freopen("test.txt", "r", stdin);
#else
	SetFile(haoi2015_t3);
#endif
#ifdef FREAD
	fread(fread_ptr, 1, FREADLENTH, stdin);
#endif
	init();
	work();
 
#ifdef DEBUG
	printf("\n%.3lf sec\n", (double)clock() / CLOCKS_PER_SEC);
#endif
	return 0;
}