题解

问题分析

给定一个整数数组，我们需要判断该数组是否是“好的”数组。数组是好的，当且仅当存在两个数字 (i) 和 (j)（满足 (1 \leq i < j \leq n)），使得对于所有 (k)（(1 \leq k \leq n)），数组中的每个元素 (a_k) 要么能被 (a_i) 整除，要么能被 (a_j) 整除。

具体来说，问题的核心是判断是否能找到两个数字 (a_i) 和 (a_j) 使得其他元素都能被这两个数字之一整除。

思路

1. 观察条件：

   • 对于数组中的任意一个元素 (a_k)，它必须能被 (a_i) 或者 (a_j) 整除。换句话说，至少存在两个数字使得其他数字能被这两个数字之一整除。

2. 求解步骤：

   • 选出数组中的最小值 (x)，然后筛选出不能被 (x) 整除的元素，再从这些元素中选出第二小的值 (y)。
   • 然后检查所有数组元素，判断每个元素是否能够被 (x) 或 (y) 整除。
   • 如果所有元素都符合这个条件，那么该数组就是好的，反之则不是。

3. 时间复杂度：

   • 对于每个查询，我们首先遍历数组找最小值和第二小值，时间复杂度为 (O(n))。
   • 然后我们再次遍历数组检查每个元素是否能被 (x) 或 (y) 整除，时间复杂度也是 (O(n))。
   • 因此，总的时间复杂度为 (O(n))。

解题代码

#include <bits/stdc++.h>
using namespace std;

bool chk(int a[], int n) {
    int x = INT_MAX, y = INT_MAX;

    // 找到最小值 x
    for (int i = 0; i < n; ++i) {
        x = min(x, a[i]);
    }

    // 找到不能被 x 整除的最小值 y
    for (int i = 0; i < n; ++i) {
        if (a[i] % x != 0) {
            y = min(y, a[i]);
        }
    }

    // 检查所有元素是否能被 x 或 y 整除
    for (int i = 0; i < n; ++i) {
        if (a[i] % x != 0 && a[i] % y != 0) {
            return false; // 如果某个元素既不能被 x 也不能被 y 整除，则返回 false
        }
    }
    return true; // 如果满足条件，返回 true
}

int main() {
    int t;
    cin >> t; // 读取询问次数
    while (t--) {
        int n;
        cin >> n; // 读取数组长度
        int a[n];
        for (int i = 0; i < n; ++i) cin >> a[i]; // 读取数组元素
        cout << (chk(a, n) ? "Yes" : "No") << endl; // 判断数组是否符合条件并输出结果
    }
    return 0;
}

##不过这个C++的代码显示时间超限然后我用Python做了一下Python的这个思路是可以下面是Python的代码

解题代码

def chk(a):
    x = min(a)
    y = float('inf')

    for num in a:
        if num % x != 0:
            y = min(y, num)

    for num in a:
        if num % x != 0 and num % y != 0:
            return False
    return True


def main():
    t = int(input())
    for _ in range(t):
        n = int(input())
        a = list(map(int, input().split()))
        print("Yes" if chk(a) else "No")


if __name__ == "__main__":
    main()