【GESP真题解析】第 13 集 GESP 三级 2024 年 6 月编程题 2：寻找倍数
大家好，我是莫小特。
这篇文章给大家分享 GESP 三级 2024 年 6 月编程题第 2 题：寻找倍数。
题目链接
洛谷链接：B4004 寻找倍数
一、完成输入
根据输入格式的描述，输入第一行整数 t，表示测试组数，数据范围：1\le t\le 10，使用 int，接着再输入 n，表示输入的序列长度，数据范围：1\le n\le 10^5，同样使用 int，输入 n 个整数，表示序列中的每一个数，数据范围：1\le a_i \le 10^9，使用 int 也合适。
int t;
cin>>t;
for(int i=1;i<=t;i++)
{
int n;
cin>>n;
}
cpp
两行的输入完成后，我们判断一下该使用什么数据结构存储数据，因为要输入 n 个数，这 n 个数需要存储判断，因此使用数组，数组需要确定好元素个数，因为 n 的数据范围，所以我们可以定义好数组。
int a[100005];
cpp
或者可以使用常量，更建议使用这个！
const int N=1e5+10;//设置常量为 100005
int a[N];
cpp
数组定义完成后，我们就要输入数组了。
for(int i=1;i<=n;i++)
{
cin>>a[i];
}
cpp
输入完成后，我们开始分析题意。
二、分析题意
根据题目描述，我们判断是否存在某个数 a_i，使得它是序列中所有数的倍数 。
也就是要找到一个数，这个数，它能被其他数整除。
要想在数组中找到是否存在一个数能否被其他数整除，就要在这个数组中找最大值。
最大值的判断，使用 max 函数，定义一个新的变量 x，将其设为最大值的初始化，使用 max 函数需要用到 #include<algorithm> 头文件，用来找到两个数中的最大值。
int x=0;
for (int i=1;i<=n;i++)
{
cin>>a[i];
x=max(x,a[i]); // 使用 max 函数找最大值
}
cpp
这样我们就通过不断更新 x = max(x, a[i])，把整个数组中最大的那个数记录到变量 x 中。
也可以用最简单的方法，直接给输入的数组进行排序，使用 sort 函数，同样也需要用到用到 #include<algorithm> 头文件。
sort(a+1,a+1+n);
cpp
因为 sort 函数默认是升序排序（也就是从小到大）最大值就是 a[n-1]。
之后就需要将数据和最大值进行处理。
看是否整除，我们可以初始化一个变量，将其标记为是否存在这个数。
int flag = 0; // 标记是否存在不整除的数
cpp
如果在其中不整除的，直接标记。
for (int i = 1; i <= n; i++)
{
if (x % a[i] != 0)
{
flag=1;
}
}
if(flag!=0)
{
cout<<"No"<<endl;
}
else
{
cout<<"Yes"<<endl;
}
cpp
如果用了 sort 函数，我们直接不遍历最后一个即可。
for (int i = 1; i < n; i++)
{
if (a[n-1] % a[i] != 0)
{
flag=1;
}
}
if(flag!=0)
{
cout<<"No"<<endl;
}
else
{
cout<<"Yes"<<endl;
}
cpp
测试一下数据。
符合样例输出，我们到网站提交评测。
三、验证数据
提交到网站中，通过！
四、完整代码
完整代码如下：
（1）变量版代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main() {
int t;
cin >> t;
for(int i=1;i<=t;i++)
{
int n;
cin >> n;
int x = 0; // 记录最大值
for (int i = 1; i <= n; i++)
{
cin >> a[i];
x = max(x, a[i]); // 找最大值
}
int flag = 0; // 标记是否存在不整除的数
for (int i = 1; i <= n; i++)
{
if (x % a[i] != 0)
{
flag = 1;
}
}
if (flag!=0)
{
cout << "No\n";
}
else
{
cout << "Yes\n";
}
}
}
cpp
（2）排序版代码
#include <bits/stdc++.h>
using namespace std;
const int N = 1e5 + 10;
int a[N];
int main() {
int t;
cin >> t;
for(int i=1;i<=t;i++)
{
int n;
cin >> n;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
}
sort(a+1,a+1+n);
int flag = 0; // 标记是否存在不整除的数
for (int i = 1; i <= n; i++)
{
if (a[n-1] % a[i] != 0)
{
flag = 1;
}
}
if (flag!=0)
{
cout << "No\n";
}
else
{
cout << "Yes\n";
}
}
}
cpp
五、技巧总结
题目的意思是：判断是否存在一个数，能被数组中所有数整除。
换句话说：是否存在一个数是数组中所有数的倍数
所以就需要在数组中找最大值，之后再判断数组中的每个数是否能整除。
找最大值，有两种方法，需要看个人的使用习惯。
方法一：变量法
int x = 0;
for (int i = 1; i <= n; i++)
{
cin >> a[i];
x = max(x, a[i]);
}
cpp
方法二：函数法
sort(a + 1, a + 1 + n);
cpp
易错的地方在于：
（1）错误下标：数组从 1 开始时，排序写法为 sort(a+1, a+1+n)
（2）错误判断：应写 x % a[i] != 0，不是 a[i] % x
（3）忘记重置变量：多组测试时 flag、x 都需每次初始化 （4）忘记 include：排序或 max 需 #include<algorithm>
---end---
如果你觉得这篇文章对你有帮助，欢迎点赞、收藏、关注我哦！
我们下集见~