ST表

二分+ST表求gcd

题目链接：https://codeforces.com/contest/1548/problem/B

题意

由不同正整数组成的数组a,求最大子数组的长度，使得存在正整数且 mod m = mod m = = mod m.

题解

    由gcd的性质可知，,所以要判断一个子区间是否满足模m相等，只需要建立一个差分数组，最终使得区间的gcd值大于1即可；考虑到本题是静态的数据，且gcd值满足结合律，所以我们可以对GCD值建立一个ST表，就能够高效地查询区间GCD的值.
    接下来，我们枚举左端点l,可以通过二分查找的方式到符合条件的最右端，再对每一个值进行维护最大值的操作.

code:

#include
#define int long long
#define endl '\n' 
#define INF 1e15
using namespace std;
typedef pairpii;
int a[200010], diff[200010][35];
signed main(){
    std::ios::sync_with_stdio(false);cin.tie(0);
    int t;cin >> t;
    while(t--){
        int n;cin >> n;
        for (int i = 1; i <= n;i++)cin >> a[i];
        n--;
        auto gcd = [&](auto gcd, int a, int b) -> int{
            return b == 0 ? a : gcd(gcd, b, a % b);
        };
        auto init = [&]() -> void{
            for (int i = 1; i <= n;i++)
                diff[i][0] = abs(a[i + 1] - a[i]);
            for (int j = 1; (1 << j) <= n;j++)
                for (int i = 1; i + (1 << j) - 1 <= n;i++)
                    diff[i][j] = gcd(gcd, diff[i][j - 1], diff[i + (1 << (j - 1))][j - 1]);
        };
        auto query = [&](int l, int r) -> int{
            int len = log2(r - l + 1);
            return gcd(gcd, diff[l][len], diff[r - (1 << len) + 1][len]);
        };
        init();
        int maxn = 1;
        for (int i = 1; i <= n;i++){
            int l = i, r = n, ans = i - 1;
            while (l <= r){
                int mid = l + r >> 1;
                if (query(i, mid) != 1)
                    l = mid + 1, ans = mid;
                else
                    r = mid - 1;
            }
            maxn = max(maxn, ans - i + 2);
        }
        cout << maxn << endl;
    }
    return 0;
}