题目描述

难度分:$1700$

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

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

然后输入$q$个询问，每个询问输入两个数$L$、$R(1 \leq L \leq R \leq n)$。

对于每个询问，输出最大的$m$，满足$a[L],a[L+1],…,a[R]$关于模$m$同余（这些数模$m$的结果都相等）。如果$m$可以无限大，输出$0$。

输入样例

3
5 5
5 14 2 6 3
4 5
1 4
2 4
3 5
1 1
1 1
7
1 1
3 2
1 7 8
2 3
1 2

输出样例

3 1 4 1 0 
0 
1 6 

算法

差分数组+$ST$表

对于任意两个数$a[i]$和$a[j]$，如果要满足$a[i] \% m=a[j] \% m$，那么任意数对$(i,j)$都有$(a[i]-a[j]) \% m$值相等成立。

而对于查询区间$[L,R]$，要想这个区间里面的任意数对$(i,j)$的$(a[i]-a[j]) \% m$相等，其实并不需要枚举数对$(i,j)$，只要相邻元素$a[L+1]-a[L],a[L+2]-a[L+1],…,a[R]-a[R-1]$模$m$的值相等就可以了。假设$i \lt j \lt k$，有$(a[j]-a[i]) \% m=(a[k]-a[j]) \% m$成立，$(a[i]-a[k]) \% m=(a[j]-a[i]) \% m=(a[k]-a[j]) \% m$仍然会满足。

这样可以先预处理出一个$diff$数组，$diff[i]=a[i]-a[i-1]$。对于任意询问$[L,R]$：

1. 如果$L=R$，那$m$可以无穷大，答案是$0$。
2. 如果$L \lt R$，那$m$就是$a[L+1]-a[L],a[L+2]-a[L+1],…,a[R]-a[R-1]$的最大公约数，求一个$diff$在$[L+1,R]$上的最大公约数即可。

考虑到本题并不会修改$a$数组，求区间最大公约数可以预处理出一个$gcd$的$ST$表，这样就能$O(1)$求得区间最大公约数了。

复杂度分析

时间复杂度

将求最大公约数的时间复杂度近似看成常数，预处理出$ST$表的时间复杂度为$O(nlog_2n)$。有了$ST$表，后续的每个询问就可以$O(1)$计算出来，因此后面询问的时间复杂度为$O(q)$。因此，整个算法的时间复杂度为$O(nlog_2n+q)$。

空间复杂度

空间消耗包括两个部分，一个是$a$的差分数组$diff$，它和$a$同规模，消耗空间为$O(n)$。另一个是$ST$表，空间消耗为$O(nlog_2n)$。因此，空间瓶颈在于$ST$表，整个算法的额外空间复杂度为$O(nlog_2n)$。

C++ 代码

#include <bits/stdc++.h>

using namespace std;
const int N = 200010, M = 19;
int T, n, q, a[N], diff[N], st[N][M];

int query(int l, int r) {
    int k = log2(r - l + 1);
    return __gcd(st[l][k], st[r - (1<<k) + 1][k]);
}

int main() {
    scanf("%d", &T);
    while(T--) {
        scanf("%d%d", &n, &q);
        for(int i = 1; i <= n; i++) {
            scanf("%d", &a[i]);
            if(i >= 2) diff[i] = abs(a[i] - a[i - 1]);
        }
        for(int j = 0; j < M; j++) {
            for(int i = 1; i + (1 << j) - 1 <= n; i++) {
                if(!j) {
                    st[i][j] = diff[i];
                }else {
                    st[i][j] = __gcd(st[i][j - 1], st[i + (1<<(j - 1))][j - 1]);
                }
            }
        }
        while(q--) {
            int l, r;
            scanf("%d%d", &l, &r);
            printf("%d ", l < r? query(l + 1, r): 0);
        }
        puts("");
    }
    return 0;
}