数组倍数判断算法与优化实践

1. 题目分析与解题思路

这道题目要求我们判断给定的数组中是否存在一个数，使得它是其他所有数的倍数。换句话说，我们需要找出数组中的最大值，然后检查这个最大值是否能被数组中其他所有元素整除。

1.1 题目理解

题目输入格式为：

• 第一行输入测试用例数量t
• 对于每个测试用例：
  • 第一行输入数组长度n
  • 第二行输入n个整数

输出要求：

• 如果数组中存在一个数是其他所有数的倍数，输出"Yes"
• 否则输出"No"

1.2 算法选择

最直观的解法是：

1. 找出数组中的最大值
2. 检查这个最大值是否能被数组中所有其他元素整除

这种解法的时间复杂度是O(n)，对于每个测试用例来说效率很高，完全能够满足题目要求。

2. 代码实现详解

2.1 基础代码结构

cpp复制#include<iostream>
#include<vector>
using namespace std;

int main(){
    int t;
    cin>>t;
    while(t--){
        int n;
        cin>>n;
        int A[n];
        // 其余代码...
    }
}

这段代码首先读取测试用例数量t，然后进入循环处理每个测试用例。对于每个测试用例，读取数组长度n和数组元素。

2.2 核心逻辑实现

cpp复制int flag = true;
int m = 0;

// 读取数组并找出最大值
for(int i=0;i<n;i++){
    cin>>A[i];
    m = max(m,A[i]);
}

// 检查最大值是否能被所有其他元素整除
for(int i=0;i<n;i++){
    if(m % A[i] == 0){
        continue;
    }else{
        flag = false;
    }
}

这里使用flag变量来记录检查结果。初始设为true，如果发现任何元素不能被最大值整除，就将flag设为false。

2.3 输出结果

cpp复制if(flag == false){
    cout<<"No"<<endl;
}els