AtCoder题解｜ABC 125C GCD on Blackboard

题目信息 📚

【题目描述】

There are $N$ integers, $A_1, A_2, …, A_N$, written on the blackboard.

You will choose one of them and replace it with an integer of your choice between $1$ and $10^9$ (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.

【输入】

Input is given from Standard Input in the following format:

$N$

$A_1, A_2, \ldots, A_N$

【输出】

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

【数据范围】

All values in the input are integers.

$2 \leq N \leq 10^5$
$1 \leq A_i \leq 10^9$

【输入样例1】

3
7 6 8

【输出样例1】

For example, 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.

【输入样例2】

3
12 15 18

【输出样例2】

【输入样例3】

2
1000000000 1000000000

【输出样例3】

1000000000

We can replace an integer with itself.

【题目来源】

https://atcoder.jp/contests/abc125/tasks/abc125_c

题目解析 🍉

【题目分析】

枚举 + 前缀$gcd$/后缀$gcd$

$gcd$ 的一条性质：若 $c = gcd(a_1, a_2, \ldots, a_n)$，则 $d = gcd(a_1, a_2, \ldots, a_n,a_{n+1}) \leq c$

这条性质告诉我们，当增加一个数时，最大的 $gcd$ 并不会增加，而且很有可能减少。所以最优的做法是把当前增加的数替换成最大的 $gcd$，这样就不会出现 $gcd$ 减少的情况。

这种替换达到的效果和去掉这个增加的数是一样的，所以我们干脆不替换新增的数，直接去掉就行了。

这样，我们就可以采用暴力做法，枚举去掉 $a_i$ 的最大 $gcd$：

$ans_i = gcd(a_1, a_2, \ldots, a_{i-1}, a_{i+1},\ldots,a_n)=gcd(gcd(a_1, a_2, \ldots, a_{i-1}), gcd( a_{i+1},\ldots,a_n))$

$ans = max(ans_1, ans_2, ans_3,\ldots,ans_n)$

如果采用纯暴力做法，对于每一个 $a_i$ 都求一遍 $gcd(a_1, a_2, \ldots, a_{i-1}), gcd( a_{i+1},\ldots,a_n)$，时间复杂度为 $O(n^2)$，会超时 TLE

所以需要采用类似前缀和/后缀和的思想，用 $O(n)$ 预处理求解：

$pre_i = gcd(a_1, a_2, \ldots, a_{i})$
- $pre_i = gcd(pre_{i-1}, a_i)$
$back_i = gcd( a_{i},\ldots,a_n)$
- $back_i = gcd(back_{i+1}, a_i)$

这样枚举 $a_i$ 时，即可在 $O(1)$ 的时间内求解 $ans_i$：

$ans_i = gcd(gcd(a_1, a_2, \ldots, a_{i-1}), gcd( a_{i+1},\ldots,a_n))=gcd(pre_{i-1},back_{i+1})$

【C++代码】

#include<bits/stdc++.h>

using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
int n, a[N], pre[N], back[N];

int main() {
    ios::sync_with_stdio(false);  //cin读入优化
    cin.tie(0);

    cin >> n;
    for (int i = 1; i <= n; i++) cin >> a[i];

    // 计算前缀gcd数组（如pre[i]表示 gcd(a[1], a[2], ...,a[i])）
    pre[1] = a[1];
    for (int i = 2; i <= n; i++) pre[i] = __gcd(pre[i - 1], a[i]);

    // 计算后缀gcd数组（如back[i]表示 gcd(a[n], a[n-1], ...,a[i])）
    back[n] = a[n];
    for (int i = n - 1; i >= 1; i--) back[i] = __gcd(back[i + 1], a[i]);

    // 枚举，消去每个数能够得到的最大值
    int ans = 1;
    for (int i = 1; i <= n; i++) {
        ans = max(ans, __gcd(pre[i - 1], back[i + 1]));
    }
    cout << ans << endl;

    return 0;
}