数论基础

寻找倍数

这道题目考察的是数论基础和逻辑推理。虽然题目看起来需要两两比较，但通过分析可以极大地简化算法。

题目分析

核心问题：
我们需要在数组 $A$ 中找到一个数 $a_i$，使得 $a_i$ 是数组中所有数的倍数。
用数学语言描述：是否存在 $a_i$，使得对于所有的 $k$ ($1 \le k \le n$)，都有 $a_i \pmod{a_k} = 0$。

关键推理：
假设数组中满足条件的数是 $X$。

1. 既然 $X$ 是数组中所有数的倍数，那么 $X$ 一定也是数组中最大值（记为 $Max$）的倍数。
2. 如果 $X$ 是 $Max$ 的倍数，那么必然有 $X \ge Max$。
3. 但是，$Max$ 本身就是数组中最大的数，数组里不可能有比 $Max$ 还大的数。
4. 所以，$X$ 只能等于 $Max$。

结论：
我们不需要检查数组里的每一个数。只需要检查数组中的最大值，看它是否能被数组里所有的数整除即可。

• 如果最大值能被所有数整除，输出 Yes。
• 否则，输出 No。

---

解题步骤

1. 读取数据：首先读取测试用例组数 $t$。
2. 处理每组数据：
   • 读取 $n$。
   • 读取 $n$ 个整数，并在读取过程中找出最大值 (max_val)。
3. 验证条件：
   • 遍历数组中的每一个数 num。
   • 检查 max_val % num 是否等于 0。
   • 如果发现有一个数不能整除 max_val，说明条件不满足，标记为失败。
4. 输出结果：根据检查结果输出 Yes 或 No。

---

C++ 代码实现

#include <iostream>

using namespace std;

int main() {
    int t;
    cin>>t;
        while (t--) {
            int n;
            cin >> n;
            int a[n];   
            int mv = 0;
            // 1. 读取数组并找到最大值
            for (int i = 0; i < n; ++i) {
                cin >> a[i];
                if (a[i] > mv) {
                    mv = a[i];
                }
            }

            // 2. 检查最大值是否能被数组中所有数整除
            bool p = true;
            for (int i = 0; i < n; ++i) {
                // 如果最大值不能整除当前这个数，说明失败
                if (mv % a[i] != 0) {
                    p = false;
                    break;
                }
            }

            // 3. 输出结果
            if (p) {
                cout << "Yes" << endl;
            } else {
                cout << "No" << endl;
            }
        }


    return 0;
}

样例验证

输入 #1

2
3
1 2 4
5
1 2 3 4 5

执行过程：

1. 第一组：数组 [1, 2, 4]。

   • 最大值是 4。
   • 检查：4 % 1 == 0 (OK), 4 % 2 == 0 (OK), 4 % 4 == 0 (OK)。
   • 全部通过，输出 Yes。

2. 第二组：数组 [1, 2, 3, 4, 5]。

   • 最大值是 5。
   • 检查：5 % 1 == 0 (OK), 5 % 2 != 0 (Fail)。
   • 发现不能整除，输出 No。

结果与题目样例一致。