上海计算机学会2024年1月月赛C++乙组T1序列最大公约数（二）
发布时间
阅读量：
阅读量
序列最大公约数（二）
内存限制: 256 Mb时间限制: 1000 ms
题目描述
给定 n 个正整数a1,a2,...,an，你可以至多修改其中一个数字，使这 n 个数字的最大公约数尽可能的大。
请问修改后可能的最大公约数的值。
输入格式
输入共两行，
第一行：一个正整数 n
第二行：n 个正整数 a1,a2,...,an
输出格式
输出至多修改一个数字的情况下，可能达到的最大公约数的值
数据范围
- 30% 的数据，1≤n≤10^3
- 60% 的数据，1≤n≤10^4
- 100% 的数据，1≤n,≤10^5 ，1≤ai≤10^9
样例数据
输入:
3
24 28 36
输出:
12
说明:
修改28，改成12即可
输入:
3
10 10 10
输出:
10
解析：
本题需要去掉一个数，求剩下的数的最大公约数，找最大值，可以枚举去掉的数，求剩下的数的最大公约数，时间复杂度为O(N^2logN),可以先预处理从第一个数到第i（1到n）个数的最大公约数和从第n个数到第i（n到1）个数的最大公约数，然后再枚举去掉的数，求最大公约数，时间复杂度O(NlogN），详见代码：
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005];
int q[100005];//q[i]表示从第1个数到第i个数的最大公约数
int h[100005];//h[i]表示从第n个数到第i个数的最大公约数
int gcd(int x,int y){//辗转相除法求xy的最大公约数
if(x%y==0) return y;
return gcd(y,x%y);
}
int main() {
cin>>n;
for(int i=1;i<=n;i++){
cin>>a[i];
}
q[1]=a[1];
//求第1个数到第i个数的最大公约数
for(int i=2;i<=n;i++){
q[i]=gcd(q[i-1],a[i]);
}
h[n]=a[n];
//求第n个数到第i个数的最大公约数
for(int i=n-1;i>=1;i--){
h[i]=gcd(h[i+1],a[i]);
}
//取去掉第一个数或去掉第n个数的最大公约数
int ans=max(h[2],q[n-1]);
for(int i=2;i<n;i++){//枚举去掉第i（2到n-1）个数
ans=max(ans,gcd(q[i-1],h[i+1]));//取最大公约数
}
cout<<ans;
return 0;
}
AI写代码cpp
全部评论 (0)
还没有任何评论哟~