C++ 查找数组中互不整除的数并输出最小余数 - 代码解析及优化

这段代码是一个查找数组中两个数是否互不整除的问题。首先，代码读取了一个整数n作为数组长度，然后读取n个整数存储在数组a中。接下来，对数组a进行排序。然后，使用嵌套循环遍历数组a中的元素，查找两个互不整除的数，并记录最小的互不整除的余数。最后，如果找到了互不整除的数，则输出最小的互不整除的余数，否则输出"NO"。\n\n需要注意的是，这段代码使用了C++标准库中的vector和algorithm头文件，并使用了命名空间std。另外，要注意isCompatible函数的定义，它判断两个数是否互不整除的方法是通过判断两个数取模是否不等于0。\n\n代码优化：\n1. 使用二分查找代替嵌套循环，可以将时间复杂度从O(n^2)降低到O(n log n)。\n2. 可以使用更简洁的判断互不整除的条件，例如直接判断a[i] % a[j] != 0。\n3. 可以使用更有效的排序算法，例如快速排序或归并排序。\n\n代码示例：\n\nc++\n#include <iostream>\n#include <vector>\n#include <algorithm>\n\nusing namespace std;\n\nboolean isCompatible(int a, int b) {\n return a % b != 0;\n}\n\nint main() {\n int n;\n cin >> n;\n\n vector<int> a(n);\n for (int i = 0; i < n; i++) {\n cin >> a[i];\n }\n\n sort(a.begin(), a.end());\n\n int minCompatibility = INT_MAX;\n bool hasCompatible = false;\n\n for (int i = 0; i < n; i++) {\n for (int j = i + 1; j < n; j++) {\n if (isCompatible(a[i], a[j])) {\n minCompatibility = min(minCompatibility, a[j] % a[i]);\n hasCompatible = true;\n }\n }\n }\n\n if (hasCompatible) {\n cout << minCompatibility << endl;\n } else {\n cout << "NO" << endl;\n }\n\n return 0;\n}\n\n\n使用说明：\n1. 编译并运行代码。\n2. 输入数组的长度n。\n3. 输入n个整数作为数组元素。\n4. 代码将输出最小的互不整除的余数，或者输出"NO"表示没有找到互不整除的数。