G3010 [GESP202406 三级] 寻找倍数 题解

知识点：一维数组、最值、整除判断。

解题思路

找出数组最大值m，检查每个元素是否都是m的因数，全部整除才输出Yes。

为什么正确

若某个数组元素是所有元素的倍数，它不能小于数组最大值，故只可能是最大值；逐项检查充分必要。

易错点

检查m%x而非x%m；题目正整数保证除数不为0。

复杂度

每组时间O(n)，空间O(n)。

参考代码（C++17）

#include<bits/stdc++.h>

using namespace std;
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int t;
    cin>>t;
    while(t--) {
        int n;
        cin>>n;
        vector<int>a(n);
        for(int &x:a)cin>>x;
        int m=*max_element(a.begin(),a.end());
        bool ok=true;
        for(int x:a)if(m%x)ok=false;
        cout<<(ok?"Yes":"No")<<"\n";
    }
}

说明

本题解为配套教学整理，非官方题解。复杂度按本页参考实现计算，题库使用6个自行生成的测试点。