思路：数论 + 思维技巧

由于题目的操作基于每个数的公因数，我们考虑将每个数质因分解进行考虑。

例如题目给的例子:

18 = 2 * 3 * 3

18 = 2 * 3 * 3

36 = 2 * 2 * 3 * 3

->

3 = 3

18 = 2 * 3 * 3

6 = 2 * 3

->

1 = 1

6 = 2 * 3

6 = 2 * 3

->

我们发现

1.一次操作等价于去掉两个数之间公因数的指数。

2.如果序列arr中存在一个质数x且其他数中均不存在x的因数。那么该序列一定失败。

这两个性质引导我们从每个质数上考虑，也就是：把每个数中的每个质数都恰好消灭 等价于 变成全1序列。

例如在prime = 2 时,

18 = 2

18 = 2

36 = 2 * 2

->

1 1 2 -> 0 1 1 -> 0 0 0

细心的人不难发现，现在我们的操作变为：任意选择两个数，将其-k (k > 0) ，问是否存在方案使得这个序列变为全0序列。

那么成功条件是:1.总和为偶数 2.最大的数不超过其他数之和

第一条显然，因为每次我们是让总数 - 2 * k ，总和为奇数，最后一定会剩下。

第二条，如果最大的数 <= 其他数总和。我们总是可以先对其他数操作，使得其他数 = 最大的数，接着每次选一个其他数 以及 选最大数 -1，反复进行即可抵消。

最后，由于t很大，我们考虑先素数筛筛出每个数的质因分解，然后对 每个数组，先map存储对数组在不同素数下的指数序列。然后对于每个质数下的指数序列考虑成功条件。

例如样例: 18 , 18 , 36

->

2,3,3 | 2,3,3 | 2,2,3,3

->

{2 : {1,1,2} , 3:{2,2,2}}

->

prime = 2 -> 1 , 1 , 2 -> 0 , 1 , 1 -> 0 , 0 , 0 -> 成功

prime = 3 -> 2 , 2 , 2 -> 1 , 1 , 2 -> 0 , 1 , 1 -> 0,0,0 -> 成功

输出:YES

代码

python

t = int(input())
# 素数筛
maxn = 2*10**5 + 1
prime = [True] * maxn
fact = [[] for _ in range(maxn)]
for i in range(2, maxn):
    if prime[i]:
        for j in range(i, maxn, i):
            prime[j] = False
            tmp = j
            cnt = 0
            # 计算i的次数
            while tmp % i == 0:
                cnt += 1
                tmp //= i
            fact[j].append([i, cnt])
# fact代表每个数的质因数分解
# 例如fact[60] = [[2, 2], [3, 1], [5, 1]]
# 60 = 2^2 * 3^1 * 5^1 
for _ in range(t):
    n = int(input())
    a = list(map(int, input().split()))
    # mp代表每个数的质因数分解的次数
    mp = {}
    for x in a:
        for p, c in fact[x]:
            if p not in mp:
                mp[p] = []
            mp[p].append(c)
    ok = True
    # 分不同质数来考虑是否能归0
    for x in mp:
        mx = max(mp[x])
        # s代表除了最大的次数之外的次数之和
        s = sum(mp[x]) - mx
        # 如果s+mx是奇数或者s小于mx，那么就不行
        if (s + mx) % 2 == 1:
            ok = False
        if s < mx:
            ok = False
        if not ok:
            break
    if ok:
        print("YES")
    else:
        print("NO")

OJ会员可以通过点击题目上方《已通过》查看其他通过代码来学习。

题目内容

​ 小红喜欢全都是$1$的数组，他有一个大小为$n$的数组$a$。

​ 小红每次操作可以选择一对$i,j$($i≠j$),然后使得$a_i,a_j$同时除以这两个数字的任意一个公因数，小红想知道他是否可以在若干次操作后将数组变成全都是$1$的数组。

输入描述

每个测试文件均包含多组测试数据。第一行输入一个整数$T$($1≤T≤2×10^5$)代表数据组数，每组测试数据如下：

第一行输入一个整数$n$($1≤n≤2×10^5$)表示数组长度。

第二行输入$n$个整数表示数组$a_1,a_2,...,a_n$($1≤a_i≤2×10^5$)。

​ 除此之外，保证所有的$n$之和不超过$2×10^5$

输出描述

对于每次询问，如果可以把数组变成全都是$1$的数组，则输出”$YES$“,否则输出”$NO$“。

样例1

输入

2
3 
18 18 36
3
3 2 1

输出

YES
NO

说明

对于第一组测试数据：

• 将第一、三个数字同时除以$6$，得到{$3,18,6$};
• 将第二、三个数字同时除以$6$，得到{$3,3,1$};
• 将第一、二个数字同时除以$3$，得到{$1,1,1$};