题目描述

Calin 有 $n$ 个桶，第 $i$ 个桶中有 $a_i$ 个边长为 $1$ 的木块。

Calin 能否用所有给定的木块拼成一个正方形？

输入格式

第一行包含一个整数 $t$（$1 \leq t \leq 10^4$），表示测试用例的数量。

每个测试用例的第一行包含一个整数 $n$（$1 \leq n \leq 2 \cdot 10^5$），表示桶的数量。

每个测试用例的第二行包含 $n$ 个整数 $a_1, \ldots, a_n$（$1 \leq a_i \leq 10^9$），表示每个桶中的木块数量。

所有测试用例中 $n$ 的总和不超过 $2 \cdot 10^5$。

输出格式

对于每个测试用例，如果 Calin 能用所有给定的 $1 \times 1$ 木块拼成一个正方形，输出 "YES"；否则输出 "NO"。

输出答案时不区分大小写（例如 "yEs"、"yes"、"Yes" 和 "YES" 都会被识别为正答）。

样例

5
1
9
2
14 2
7
1 2 3 4 5 6 7
6
1 3 5 7 9 11
4
2 2 2 2

YES
YES
NO
YES
NO

样例说明

在第一个测试用例中，Calin 可以拼成一个 $3 \times 3$ 的正方形。

在第二个测试用例中，Calin 可以拼成一个 $4 \times 4$ 的正方形。

在第三个测试用例中，Calin 不能用所有给定的木块拼成一个正方形。

由 ChatGPT 4.1 翻译

来源

Codeforces 1915C，英文题名 Can I Square?。