Solution - CF1549D

Solution

首先，注意到对于两个数$a_i, a_j$，$m$的最大值为$\left|a_i - a_j\right|$，且可以取到。

对于$a_i, a_{i + 1}, \cdots, a_j$，$m$的最大值为$\gcd(\left|a_i - a_{i + 1}\right|, \cdots, \left|a_{j - 1} - a_j\right|)$，且可以取到，因为：

1. $m$如果比$\gcd(\left|a_i - a_{i + 1}\right|, \cdots, \left|a_{j - 1} - a_j\right|)$大，那么一定存在$\left|a_k - a_{k + 1}\right| \not\equiv 0\mod m\iff a_k - a_{k + 1}\neq km(k\in\textbf{Z})$，矛盾。
2. $m=\gcd(\left|a_i - a_{i + 1}\right|, \cdots, \left|a_{j - 1} - a_j\right|)$时，任意两个数$a_k - a_h = (a_k - a_{k + 1}) + (a_{k + 1} - a_{k + 2}) + \cdots + (a_{h - 1} - a_h) = (k_1 + k_2 + \cdots k_{h - k})m$，所以满足条件。

根据以上分析，确定区间就可以直接求出$m$。这个时候有两种解决方法：

1. 利用倍增，每个数往后倍增直到$m=1$，时间复杂度$O(n\log n\log \max a_i)$。利用st表可以做到$O(n\log\max a_i + n\log n)$。
2. 利用baka's trick进行双指针：每一时刻都有三个指针：$l, r, mid$，其中$mid\in [l, r]$，并且每一时刻$[l, mid], [l + 1, mid], \cdots, [mid - 1, mid]$的贡献已经处理好。当$l$要跨越$mid$的时候，将$mid$设为$r$，并让$l$从$r$倒序遍历回来，处理好新的$[l, mid], [l + 1, mid], \cdots, [mid - 1, mid]$的贡献。通过这样反复横跳，可以实现无删的双指针（只要单调且可加就可以双指针）。由于$r$总共动$n$次，$mid$是单调增加的，也最多总共动$n$格，而$l$除了本身要动的$n$下，最多再把$mid$走的路径走一遍，也是只要动$O(n)$下。故要计算的次数还是$O(n)$的。这样时间复杂度就是$O(n\log\max a_i)$。

Code

Show Code

#include<bits/stdc++.h>
typedef long long LL;
using namespace std;
const int N = 2e5 + 1;
LL A[N], B[N], rev[N]; int n;
inline LL gcd(LL a, LL b){
    while (b){
        a %= b;
        a ^= b ^= a ^= b;
    }
    return a;
}
signed main(){
    int t; cin >> t;
    while (t--){
        cin >> n;
        for (int i = 1; i <= n; ++i) cin >> A[i];
        for (int i = 1; i < n; ++i) B[i] = abs(A[i] - A[i + 1]), rev[i] = 0;
        int l = 1, mid = 0;
        int ans = 1;
        LL sum = 0;
        for (int r = 1; r < n; ++r){
            sum = gcd(sum, B[r]);
            while (l <= mid && gcd(sum, rev[l]) == 1) ++l;
            if (l > mid){ // 超过mid时重新计算
                mid = r, rev[mid] = B[mid];
                for (int i = mid - 1; i >= l; --i){
                    rev[i] = gcd(rev[i + 1], B[i]);
                }
                sum = 0;
            }
            while (l <= mid && gcd(sum, rev[l]) == 1) ++l;
            ans = max(ans, r - l + 2);
        }
        cout << ans << endl;
    }
    return 0;
}

---