题目传送门: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; }
Comments NOTHING