• 题目描述

  • There are N integers, A1,A2,…,AN, written on the blackboard.
    You will choose one of them and replace it with an integer of your choice between 1 and 109 (inclusive), possibly the same as the integer originally written.

  • Find the maximum possible greatest common divisor of the N integers on the blackboard after your move.

  • Constraints
    ·All values in input are integers.
    ·2≤N≤105
    ·1≤Ai≤109

  • 输入
    Input is given from Standard Input in the following format:

  • N
    A1 A2 … AN

  • 输出
    Print the maximum possible greatest common divisor of the N integers on the blackboard after your move.

  • 样例输入 Copy
    3
    7 6 8

  • 样例输出 Copy
    2

  • 提示
    If we replace 7 with 4, the greatest common divisor of the three integers on the blackboard will be
    2, which is the maximum possible value.

  • 题意：给出一些数，改这写数中的一个数，使这些数的gcd最大，求这些数的gcd。

  • 思路；类似前缀和，后缀和的形式，把前后缀gcd写出来，既然他要改一个数就是前面数的gcd 与后面数的gcd 求gcd；简单的说，假设改第i个就是gcd(前缀(i-1)gcd,后缀(i+1)gcd)直接把第i个数跳过去就是把它改成他们的gcd。这样就是最大。说的有点复杂。其实理解起来就很简单了。

  • 代码 ：

#include<iostream>
#include<math.h>
#include<stdio.h>
#include<string.h>
#include <algorithm>
#include <bits/stdc++.h>
#define ll long long int
#define sc(a) scanf("%lld",&a)
const int mod=998244353;
using namespace std;
const int inf=1e9+7;
const int maxn=2e5+10;
 
ll n,m;
int sum,t,p,res;
int a[maxn],b[maxn],c[maxn];
ll x,y;
ll dp[110][110];
ll maxx=-1,num=-1;
char str[maxn],s[maxn],ss[maxn];
 
int gcd (int a,int b){
    while(b){
        int t=a%b;
        a=b;
        b=t;
    }
    return a;
}
 
int main(){
    scanf("%lld",&n);
    for(int i=1;i<=n;i++)
        scanf("%d",&a[i]);//x
     
    b[1]=a[1];
    for(int i=2;i<=n;i++)
        b[i]=gcd(b[i-1],a[i]);//前缀gcd 
     
    c[n]=a[n];
    for(int i=n-1;i>=1;i--)//后缀gcd 
        c[i]=gcd(c[i+1],a[i]);
     
    for(int i=2;i<n;i++)
        sum=max(gcd(b[i-1],c[i+1]),sum);
     
    cout<<max(sum,max(c[2],b[n-1]))<<endl;
    return 0;
}
  • 说一个我一开始的想法，(可能有点可笑)；
  • 错误思路因为他是1-109，所以我直接从109开始用这些数对他取余，如果能整除这个数就记录下来，最后判断总数大于等于n-1吗？如果等，那么这个数就是我们要的gcd