Dotcpp  >  编程题库  >  蓝桥杯2022年第十三届决赛真题-分石头(C/C++组)
题目 2745:

蓝桥杯2022年第十三届决赛真题-分石头(C/C++组)

时间限制: 2s 内存限制: 512MB 提交: 112 解决: 21

题目描述

小蓝和小乔正在玩一个游戏:对给定的 n 堆石子,每次可以选一堆石子分成相等的质数份或直接消去。双方轮流操作,轮到某玩家操作时如果没有任何石子则这个玩家失败。

小蓝先操作(先手),小乔后操作。

请问小蓝是否存在必胜策略,即是不是存在一种策略,使得不论小乔如何操作,小蓝总有办法获得胜利。

输入格式

输入包含多组独立的询问。

输入的第一行包含一个整数 T 表示询问的组数。

接下来依次描述每一组询问。

每组询问的第一行包含一个整数 ni ,表示石子的堆数。

第二行包含 n 个正整数,相邻两个整数之间用一个空格分隔,依次表示每堆石子的个数。

输出格式

输出 T 行,每行包含一个整数 0 或 1,表示对应询问的答案。如果小蓝存在必胜策略,输出 1,否则输出 0 。

样例输入

2
2
2 3
5
4 15 1 9 6

样例输出

1
1

提示

对于 20% 的评测用例,T = 1 ,ni ≤ 10 ,每堆石子数量不超过 1000;

对于 50% 的评测用例,∑ ni ≤ 10000;

对于所有评测用例,1 ≤ T ≤ 105 ,1 ≤ ni , ∑ ni ≤ 105 ,每堆石子数量不超过 106

标签