ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
  • ETOJ在线评测系统
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

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

2022年4月20日 896点热度 0人点赞 0条评论

题目传送门: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;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ codeforces 双指针 差分 数论 线段树
最后更新:2022年7月9日

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

取消回复

Eriktse

18岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌摆烂人,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

文章目录
  • 题目大意
  • 思路
  • 代码

友情链接 | 站点地图

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos | Hosted In TENCENT CLOUD

赣ICP备2022001555号-1

赣公网安备 36092402000057号