[CodeForces]1549D. Integers Have Friends（线段树 + 差分 + 数论 + 双指针）

题目传送门：Problem - D - Codeforces

题目大意

有 T 组数据，给定长度为 N 的序列 A。

求符合同余条件的连续子序列的最长长度。

同余是指序列中任意两个数字Ai Aj都有同一个确定的 M 使得A i == Aj (mod M)，M >= 2。

思路

通过题意不难想到同余定理：数论中的重要概念。给定一个正整数m，如果两个整数a和b满足a-b能够被m整除，即(a-b)/m得到一个整数，那么就称整数a与b对模m同余，记作a≡b(mod m)。对模m同余是整数的一个等价关系。（引用自同余定理_百度百科 (baidu.com)）

写成推导式就是说：

也就是说只要一段差分序列的具有非1的最大公因数，那么就说明这一段的原序列是满足同余关系的。

接下来就是构造差分序列：diff[i] = | a[i] - a[i - 1] |。（不要忘记加绝对值）

然后还要对差分数组建立一棵线段树用来快速算出一段区间的gcd（最大公因数）。

这里不要对线段树进行modify，所以简单写一下build和query就够了。

在这时候用双指针来对整个序列进行查找，只要区间[i, j]的gcd != 1就说明可以再扩大，就j ++，不断更新最大值就好了。

还有一点需要注意就是初始化ans = 1，因为我们在双指针查找最大值的时候循环初始条件是i = 2 ，因为i = 1的话，i = 0不是原数组中的元素，会导致最后的答案多1，从2开始就不会有这个问题，但是N = 1的话不会进循环，所以所以要初始化ans = 1。

代码

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 2e5 + 10;
int a[maxn], diff[maxn], N;
int tree[4 * maxn];//表示gcd 

int gcd(int a,int b){return a == 0 ? b : gcd(b % a, a);}
int getabs(int x){return x < 0 ? -x : x;}
void build(int s,int e,int node)
{
	if(s == e)return tree[node] = diff[s],void();
	int mid = (s + e) / 2;
	build(s,     mid, node << 1);
	build(mid + 1, e, node<<1|1);
	tree[node] = gcd(tree[node << 1], tree[node << 1 | 1]);
}

int query(int l,int r,int s = 1,int e = N,int node = 1)
{
	if(l <= s && e <= r)return tree[node];
	if(e < l || r < s)return 0;
	
	int mid = (s + e) / 2, g1 = 0, g2 = 0, res = 0;
	if(g1 = query(l, r, s,   mid, node << 1))res = g1;
	if(g2 = query(l, r,mid + 1,e, node<<1|1))res = (res == 0) ? g2 : gcd(res, g2);
	return res;
}

signed main()
{
	int T;cin >> T;
	while(T --)
	{
		cin >> N;
		for(int i = 1;i <= N; ++ i)
		{
			scanf("%lld", a + i);
			diff[i] = getabs(a[i] - a[i - 1]);
		}
		
		build(1, N, 1);
		
		int ans = 1;
		for(int i = 2,j = 2;i <= N && j <= N; ++ i)
		{
			while(j <= N && query(i, j) != 1)j ++;
			ans = max(ans, j - i + 1);
		}
		printf("%lld\n", ans);
	}
	return 0;
}