[数据结构与算法]Integers Have Friends（线段树/gcd/双指针）

题目
题意：给定n个点，求这n个点的最长同余子串。一个序列同余，当且仅当存在数m>1，使得序列中所有数在模m的意义下相等。

参考
思路：求原数组a的相邻元素的差分数组d，问题转化为求d数组的最长连续子数组，使得该数组的gcd>1，查询连续子数组的gcd可以用线段数（没看题解，一开始竟然没反应过来orz），由于又是连续连续的，且gcd的区间查询有非递增性（即子数组的gcd一定不小于母数组的gcd），可以用双指针优化。详见代码。

#include<bits/stdc++.h> 
using namespace std;
#define ll long long
const int maxn = 200010;
#define lson (rt<<1)
#define rson (rt<<1|1)

ll a[maxn];
ll d[maxn], g[maxn<<2];


void print(ll d[], int n) {
	for (int i = 1; i < n; ++i)
		printf("%lld ", d[i]);
	printf("\n");
}
void pushup(int rt) {
	g[rt] = __gcd(g[lson], g[rson]);
}
void build(int rt, int l, int r) {
	if (l == r) {
		g[rt] = d[l];
		return;
	}
	int m = (l + r) >> 1;
	build(lson, l, m);
	build(rson, m + 1, r);
	pushup(rt);
}
ll query(int rt, int l, int r, int a, int b) {
	if (l >= a && r <= b)
		return g[rt];
	int m = (l + r) >> 1;
	ll ans = 0;
	if (a <= m)
		ans = query(lson, l, m, a, b);
	if (m < b) {
		ll tmp = query(rson, m + 1, r, a, b);
		ans = __gcd(ans, tmp);
	}
	return ans;
}
int main() {
	int t;
	scanf("%d", &t);
	while (t--) {
		int n;
		scanf("%d", &n);
		
		for (int i = 0;i < n; ++i) {
			scanf("%lld", &a[i]);
		}
		if (n == 1) {
			printf("1\n");
			continue;
		}
		for (int i = 1; i < n; ++i) {
			d[i] = abs(a[i] - a[i-1]);
		}
		build(1, 1, n - 1);
		int ans = 1;
		for (int l = 1, r = 1; r < n; ++r) {
			if (d[r] == 1) continue;
			while (l < r && query(1, 1, n - 1, l, r) == 1)
				++l;
			
			ans = max(ans, r - l + 2);
		}
		printf("%d\n", ans);
	}
	
}