本文主要是介绍上海市计算机学会竞赛平台2024年1月月赛乙组序列最大公约数（二），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题目描述
给定 𝑛n 个正整数𝑎1,𝑎2,...,𝑎𝑛a1,a2,...,an，你可以至多修改其中一个数字，使这 𝑛n 个数字的最大公约数尽可能的大。
请问修改后可能的最大公约数的值。
输入格式
输入共两行，
第一行：一个正整数 𝑛n
第二行：𝑛n 个正整数 𝑎1,𝑎2,...,𝑎𝑛a1,a2,...,an
输出格式
输出至多修改一个数字的情况下，可能达到的最大公约数的值
数据范围
- 30%30% 的数据，1≤𝑛≤1031≤n≤103
- 60%60% 的数据，1≤𝑛≤1041≤n≤104
- 100%100% 的数据，1≤𝑛,≤1051≤n,≤105 ，1≤𝑎𝑖≤1091≤ai≤109
样例数据
输入:
3
24 28 36
输出:
12
说明:
修改28，改成12即可
输入:
3
10 10 10
输出:
10
详见代码:
#include<bits/stdc++.h>
using namespace std;
int n;
int a[100005];
int q[100005];
int h[100005];
int gcd(int x,int y){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];for(int i=2;i<=n;i++){q[i]=gcd(q[i-1],a[i]);}h[n]=a[n];for(int i=n-1;i>=1;i--){h[i]=gcd(h[i+1],a[i]);}int ans=max(h[2],q[n-1]);for(int i=2;i<n;i++){ans=max(ans,gcd(q[i-1],h[i+1]));}cout<<ans;这篇关于上海市计算机学会竞赛平台2024年1月月赛乙组序列最大公约数（二）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
