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

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

时间限制: 10s 内存限制: 512MB 提交: 2 解决: 1

题目描述

小蓝和小乔正在玩一个游戏:对给定的 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 ,每堆石子数量不超过 10
标签