蓝桥杯2026年第十七届省赛真题-纯粹魔药

你是一名见习炼金术士。为了通过毕业考核，你需要熬制一瓶 “纯粹魔药”。

在你面前有 m 种魔法材料，每种材料当前的 “魔力浓度” 为一个正整数，依次记为 v1, v2, . . . , vm。

你可以对这些材料进行一种叫做 “提纯” 的魔法操作。

每次你可以选择任意一种材料，并对其施放提纯魔法：

• 如果该材料当前的魔力浓度为 x，施法后，它的魔力浓度会变成 x 的正约数的个数 d(x)。

例如：如果浓度为 6，因为 6 有 1, 2, 3, 6 共四个约数，提纯后浓度变为 4。

你可以对任意材料进行任意次提纯操作（也可以不操作）。

根据炼金术法则，只有当这 m 种材料的魔力浓度之乘积恰好是一个质数（即只能被 1 和它本身整除的大于 1 的整数，如 2, 3, 5 等）时，纯粹魔药才能熬制成功。

现在，请判断你是否有可能通过若干次操作，成功熬制出纯粹魔药。

第一行包含一个整数 T，表示测试数据的组数。

对于每组测试数据：

• 第一行包含一个整数 m，表示魔法材料的数量。

• 第二行包含 m 个整数 v1, v2, . . . , vm，表示每种材料的初始魔力浓度。

对于每个测试数据，如果能够使最终所有材料的魔力浓度乘积变为质数，输出 ‘YES’；否则输出 ‘NO’。

【评测用例规模与约定】

对于 30% 的评测用例，1 ≤ T ≤ 10，1 ≤ m ≤ 10，1 ≤ vi ≤ 100；

对于所有评测用例，1 ≤ T ≤ 1000，1 ≤ m ≤ 10⁵，1 ≤ vi ≤ 10¹⁸，且保证对于所有的测试数据，m 的总和不超过 2 × 10⁵。