美妙数组题解
为了确认数组 a 是否美丽，我们需要找到两个不同的数 a_i 和 a_j（ 其中 1 \leq i, j \leq n 且 i \neq j），使得数组中的每个元素都能被 a_i 或 a_j 整除。如果这样的两个数存在，则数组是美丽的，否则不是。
解决方案：
- 对数组进行排序：这有助于快速找到最小和次小的唯一元素。
- 找到两个最小的不同的数：这些数作为候选的 a_i 和 a_j 。
- 检查可整除性：对于数组中的每个元素，检查是否可以被这两个最小的数中的一个整除。
代码实现：
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
bool isBeautiful(vector<int>& a) {
int n = a.size(); // 获取数组的大小
sort(a.begin(), a.end()); // 对数组进行排序，从小到大排列
int first = a[0]; // 获取排序后数组的第一个元素，即最小值
int second = -1; // 初始化第二小值为-1
// 找到数组中第一个不同于first的元素，即第二小的不同元素
for (int i = 1; i < n; i++) {
if (a[i] != first) {
second = a[i];
break; // 找到第二小值后跳出循环
}
}
// 如果数组中所有元素都相同，即没有第二小值，则返回false
if (second == -1) {
return false;
}
// 检查数组中的每个元素是否可以被first或second整除
for (int i = 0; i < n; i++) {
if (a[i] % first != 0 && a[i] % second != 0) {
return false; // 只要有一个元素不能被这两个数整除，则返回false
}
}
return true; // 如果所有元素都能被first或second整除，则返回true
}
int main() {
int t;
cin >> t; // 读取测试用例的数量
while (t--) {
int n;
cin >> n; // 读取每个测试用例中数组的大小
vector<int> a(n); // 定义一个大小为n的数组
for (int i = 0; i < n; i++) {
cin >> a[i]; // 读取数组中的元素
}
// 检查数组是否美丽，并输出结果
if (isBeautiful(a)) {
cout << "Yes" << endl;
} else {
cout << "No" << endl;
}
}
return 0;
}
解释：
- 排序数组：有助于快速找到最小和次小的唯一元素。
- 找到两个最小的不同的数：这些数作为候选的 a_i 和 a_j。
- 检查每个元素的可整除性：确保数组中的每个元素都可以被这两个最小的数中的一个整除。
输入输出示例：
示例输入：
4
3
7 3 8
5
7 1 9 3 5
5
4 12 2 6 3
5
7 49 9 3 1000000000
示例输出：
No
Yes
Yes
No
示例解释：
-
第一个数组
7 3 8：- 最小值是 3，次小值是 7，检查每个数是否可以被 3 或 7 整除。发现 8 既不能被 3 整除也不能被 7 整除，所以输出 No。
-
第二个数组
7 1 9 3 5：- 最小值是 1，次小值是 3。所有数都能被其中一个整除，所以输出 Yes。
-
第三个数组
4 12 2 6 3：- 最小值是 2，次小值是 3。所有数都能被其中一个整除，所以输出 Yes。
-
第四个数组
7 49 9 3 1000000000：- 最小值是 3，次小值是 7。发现 1000000000 既不能被 3 整除也不能被 7 整除，所以输出 No。
