题目描述

难度分:$2400$

输入$T(\leq 10^5)$表示$T$组数据。所有数据的$n$之和$\leq 5 \times 10^5$。

每组数据输入$n(1 \leq n \leq 2 \times 10^5)$，长为$n$的数组$a(1 \leq a[i] \leq 10^9)$和长为$n$的数组$b(1 \leq b[i] \leq 10^9)$。

你必须执行如下操作恰好一次：

• 选择两个下标$L$和$R$，满足$L \leq R$。然后交换$a[L]$和$b[L]$，交换$a[L+1]$和$b[L+1]$，……，交换$a[R]$和$b[R]$。

定义$GCD(A)$为数组$A$中所有元素的$GCD$。输出操作后$GCD(a)+GCD(b)$的最大值，以及有多少个不同的$(L,R)$可以得到这个最大值。

输入样例

5
8
11 4 16 17 3 24 25 8
8 10 4 21 17 18 25 21
4
6 4 24 13
15 3 1 14
2
13 14
5 8
8
20 17 15 11 21 10 3 7
9 9 4 20 14 9 13 1
2
18 13
15 20

输出样例

2 36
3 2
2 3
2 36
6 1

算法

前后缀分解+logTrick

先预处理出$a$、$b$两个数组的前后缀$gcd$。

下标从$1$开始，以$r$为分割线，对于前缀$1$到$r$，需要计算：

• $GCD(a[1],…,a[l-1],b[l],b[l+1],…,b[r])$
• $GCD(b[1],…,b[l-1],a[l],a[l+1],…,a[r])$

可以用logTrick计算（维护）。

定义$res$是一个三元组列表列表，包含三个数：

1. $g1=GCD(a[1],…,a[l-1],b[l],b[l+1],…,b[i])$
2. $g2=GCD(b[1],…,b[l-1],a[l],a[l+1],…,a[i])$
3. $index=$在遍历$a,b$的过程中，这对$(g1,g2)$首次出现的下标。

从$i-1$遍历到$i$，我们可以在$res[i-1]$的$g1$的基础上，额外$GCD$一个$b[i]$，得到$res[i]$的$g1$。同理在$res[i-1]$的$g2$的基础上，额外$GCD$一个$a[i]$，得到$res[i]$的$g2$。

然后额外增加一个只交换$a[i]$和$b[i]$的结果，即：

1. $g1 = GCD(a[1],…,a[i-1],b[i])$
2. $g2 = GCD(b[1],…,b[i-1],a[i])$
3. 以及这对$(g1,g2)$首次出现的下标，也就是$i$。

为了计算这个额外增加的$(g1,g2)$，我们就可以利用$a$和$b$的前缀 $GCD$。对于每个$r$，遍历所有的$res[r]$，计算$GCD(a)+GCD(b)$的最大值。出现次数可以用$res[i]$中的两个相邻元组中的$index$之差得到。

复杂度分析

时间复杂度

预处理前后缀$gcd$的时间复杂度为$O(nlogU)$，其中$U$是数组$a$和$b$的值域。接下来的logTrick枚举，$gcd$的数量大概在$O(logn)$的级别，所以枚举的时间复杂度为$O(nlogn)$，但是这其中还有$gcd$的计算，时间复杂度大约是$O(nlognlogU)$。

空间复杂度

$res$数组中只存储了$O(logn)$级别的$gcd$信息，所以空间的瓶颈在于前后缀的$gcd$数组$pre$和$suf$，额外空间复杂度为$O(n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
typedef long long LL;

const int N = 200010;
int T, n, a[N], b[N];

struct Pair {
    int x, y;
} pre[N], suf[N];

struct Tuple {
    int g1, g2, l;
};

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d", &n);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
        }
        for(int i = 1; i <= n; i++) {
            scanf("%d", &b[i]);
        }
        suf[n + 1].x = suf[n + 1].y = 0;
        // 前后缀gcd
        for(int i = 1; i <= n; i++) {
            int j = n - i + 1;
            pre[i].x = __gcd(pre[i - 1].x, a[i]);
            pre[i].y = __gcd(pre[i - 1].y, b[i]);
            suf[j].x = __gcd(suf[j + 1].x, a[j]);
            suf[j].y = __gcd(suf[j + 1].y, b[j]);
        }
        int mx = 0;
        LL cnt = 0;
        vector<Tuple> res;
        // logtrick枚举
        for(int i = 1; i <= n; i++) {
            for(auto& p: res) {
                p.g1 = gcd(p.g1, b[i]);
                p.g2 = gcd(p.g2, a[i]);
            }
            res.push_back({__gcd(pre[i - 1].x, b[i]), __gcd(pre[i - 1].y, a[i]), i});
            int j = 1;
            for(int k = 1; k < res.size(); ++k) {
                if(res[k].g1 != res[k - 1].g1 || res[k].g2 != res[k - 1].g2) {
                    res[j++] = res[k];
                }
            }
            res.resize(j);
            int prePos = i + 1;
            for(int k = res.size() - 1; k >= 0; k--) {
                auto p = res[k];
                int s = __gcd(p.g1, suf[i + 1].x) + __gcd(p.g2, suf[i + 1].y);
                if(s > mx) {
                    mx = s;
                    cnt = prePos - p.l;
                }else if(s == mx) {
                    cnt += prePos - p.l;
                }
                prePos = p.l;
            }
        }
        printf("%d %lld\n", mx, cnt);
    }
    return 0;
}