题目描述
给定 𝑛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;