题解 P5502 【[JSOI2015]最大公约数】

saxiy · 2019-09-15 15:46:23 · 题解

UPD: 19/10/05 补充了部分说明，感谢 @LRL52 提出的错误并修正了代码。

UPD：21/06/10 修改了表述并补充了正确性证明

这题可以用区间分治的思想。在两年后的今天我才惊讶地发现《算法导论》分治章节的第一页就是这个算法。

题目分析:

在我们现在考虑的区间 [L,R] 中，设最大价值区间为 [l,r]，设 mid=\left\lfloor\frac{L+R}{2}\right\rfloor，那么它只有三种可能：

前两种情况递归就行了，边界为 L=R，以权值 a_i（即自己乘以长度 1）尝试更新答案。

然后是第三种情况，既然 l 在 [L,mid] 中，r 在 [mid,R] 中，那么必然包含了 a_{mid} 这个数，从 a_{mid} 开始向左右扩展，如果一个与当前选取的区间左右相邻的数加进来能保持当前 \gcd 不变，那么就贪心地加进来，在无法拓展时就可以尝试更新答案了，然后加进会改变 \gcd 的一个新数，又开始拓展 \dots 直到拓展到边界 L 或者 R 为止。

在加进新数改变 \gcd 时我们有两种选择，一种是加左边的，一种是加右边的，我们只需要一次以左边为准拓展完一次，再一次以右边为准即可。这样能保证考虑到这个区间所有的 \gcd 了，正确性在代码后证明。

不算 \gcd 的复杂度为 O(n\log{n})。 大家就把gcd当常数好了

代码实现(2019年，216ms in total):

//2019 last edition by saxiy，2019的古董仅作参考
#pragma GCC optimize("fast-math,unroll-loops")
#include <bits/stdc++.h>
#define RS register
#define N 100005
using namespace std;
typedef long long ll;

template <typename T> void read(T &x) {
    x = 0; RS char c(getchar());
    while(!isdigit(c)) c = getchar();
    for(;isdigit(c);c = getchar())
        x = (x << 3) + (x << 1) + (c ^ 48); 
}

int n; ll a[N];

inline ll max(ll a, ll b) { return a > b ? a : b; }

ll gcd(ll a, ll b) {//不用管这gcd
    if(!a) return b; if(!b) return a;
    if(!(a & 1 || b & 1))
        return gcd(a >> 1, b >> 1) << 1;
    if(!(a & 1)) return gcd(a >> 1, b);
    if(!(b & 1)) return gcd(a, b >> 1);
    return gcd(abs(a - b), min(a, b));
}

ll dfs(int L, int R) {
    if(L == R) return a[L];
    RS int l, r, mid = L + R >> 1;
    l = r = mid;
    RS ll g = a[mid], maxx = a[mid];
    while(L <= l && r < R) {
        g = gcd(a[++r], g);
        while(r <= R) if(a[++r] % g) break; r--;
        while(l >= L) if(a[--l] % g) break; l++;
        maxx = max(maxx, (r - l + 1) * g);
    }
    l = r = mid; g = a[mid];
    while(L < l && r <= R) {
        g = gcd(a[--l], g);
        while(l >= L) if(a[--l] % g) break; l++;
        while(r <= R) if(a[++r] % g) break; r--;
        maxx = max(maxx, (r - l + 1) * g);
    }
    return max(maxx, max(dfs(L, mid), dfs(mid + 1, R)));
}

int main() {
    read(n);
    for(RS int i = 1;i <= n;i++) read(a[i]);
    printf("%lld", dfs(1, n));
    return 0;
}

正确性证明

会用到几个易证的引理，留给读者思考就略过证明了。

1. 对于所有 a_i(i \in [L,R])，区间 [a_i,a_{mid}] 一定被拓展过。
2. 对于一个序列任意的子序列（可以不连续），子序列的 \gcd 一定 \ge 原序列的 \gcd。
3. 如果公共 \gcd 减小，至少除以 2。

定义某区间的 父区间 为此区间经两侧完全贪心拓展后的区间。

定义 最大价值区间 为其相同公共 \gcd 的子区间的 父区间，即保证目前 \gcd 不变的情况下，区间长度最大。

现在我们算法最大的问题就是只能保证每个 a_i(i \in [L,R])，区间 [a_i,a_{mid}] 被拓展过，会不会存在一个区间 [l,r] 满足 l\in [L,mid] \And r\in [mid,r] 并且我们没考虑过，事实上这样的区间是存在的，下面证明这样的区间不可能更新答案。

假设存在 最大价值区间 [l,r]（显然我们只用考虑最大价值区间）是区间 [L,R] 内的最优解，那么根据 引理1，[l,mid] 和 [mid,r] 一定被拓展过，那么存在 a_n\in[l,mid) 恰好位于 [mid,r]的 父区间 左侧相邻位置且使得 a_n 加入 [mid,r] 的 父区间 后会改变其 \gcd。同理定义 a_m\in (mid,r]。根据 引理2、3，可以得到如下不等式关系。

定义区间 [l,r] 长度为 S、\gcd 为 E，区间 [l,mid] 父区间 长度为 S_l、\gcd 为 E_l，同理定义 S_r、E_r。

不等式 1、2 描述了最优权值关系，限定了 [l,r] 能尝试更新答案。不等式 3 描述的长度关系来自于 [l,mid] 和 [mid,r] 的 父区间 至少共同包含了 a_{mid} 这个数。不等式 3、4 说明了 [l,r] 不可被拓展到的性质和 引理3。

将不等式 4 带入 1，5 带入 2 可得：

相加便和不等式 3 推出了矛盾。

所以，不存在这样的区间有机会更新答案

证毕，这就是正确性。