GESP202406 三级 寻找倍数

题目分析

给定一个序列 $A=[a_1, a_2, \dots, a_n]$，
判断是否存在某个元素 $a_i$，能整除序列中所有元素。

关键点：
若存在这样的数 $a_i$，它必然是序列中的最大值。
因为如果不是最大值，无法整除比它大的元素。

---

解题思路

• 找到序列中的最大值 mx；
• 判断是否所有元素都能被 mx 整除；
• 如果是，则输出 Yes；否则输出 No。

---

实现步骤

• 读入 $t$；
• 对每组数据：
  • 读入 $n$，读入数组 A，注意数据范围需要设定的数组大小；
  • 找到 mx，遍历一遍数组的元素即可求得最大值；
  • 检查对所有 $a_i$，mx % a[i] == 0 是否成立；
    • 初始化一个标记变量 ok = 1。
    • 若存在一个 a[i] 使得 mx % a[i] != 0 成立，则修改 ok 为 $0$。
    • 循环结束后根据 ok 的值来决定输出。

---

复杂度分析

• 时间复杂度：$O(t \times n)$，仅需遍历一次序列找最大值，一次判断；
• 空间复杂度：$O(n)$。

---

总结

• 题目关键是发现答案只可能是最大值；
• 判断最大值是否是所有元素的倍数即可；
• 逻辑简单，效率高，适合快速解题。