专栏文章

题解 CF2050F

HHYdroKomide
CF2050F题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqtv7wl
此快照首次捕获于
2025/12/04 10:39
3 个月前
此快照最后确认于
2025/12/04 10:39
3 个月前
查看原文

题意：

给定一个序列，每次询问求区间同余最大模数。

思路：

发现一些有趣的性质：考虑一个区间，如果所有数除以某个模数的余数相同，所有数之间的差一定是这个模数的倍数。反之我们有：使得区间内所有数同余的模数是区间差分的最大公约数。
区间 gcd 可以被线段树合并，于是开线段树，每次询问直接查询即可（注意区间内所有数相等时答案是 00）。复杂度 O(nlog⁡n)O(n\log n)。

程序如下：

CPP
#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
using namespace std;
const int N=2e5+5;
int T,n,q,a[N];
int bet[N],t[N*4];
int gcd(int a,int b){
	if(a==0&&b==0)return 0;
	return __gcd(a,b);
}
int ls(int x){return x<<1;}
int rs(int x){return x<<1|1;}
void pushup(int x){t[x]=gcd(t[ls(x)],t[rs(x)]);}
void build(int x,int l,int r){
	if(l==r){
		t[x]=bet[l];
		return;
	}
	int mid=(l+r)>>1;
	build(ls(x),l,mid);
	build(rs(x),mid+1,r);
	pushup(x);
}
int query(int x,int l,int r,int L,int R){
	if(L<=l&&R>=r)return t[x];
	int mid=(l+r)>>1;
	if(L<=mid&&R<=mid)return query(ls(x),l,mid,L,R);
	else if(L>mid&&R>mid)return query(rs(x),mid+1,r,L,R);
	else return gcd(query(ls(x),l,mid,L,R),query(rs(x),mid+1,r,L,R));
}
int main(){
	scanf("%d",&T);
	while(T--){
		scanf("%d%d",&n,&q);
		for(int i=1;i<=n;i++){
			scanf("%d",&a[i]);
			if(i>1)bet[i-1]=abs(a[i]-a[i-1]);
		}
		if(n>1)build(1,1,n-1);
		while(q--){
			int l,r;
			scanf("%d%d",&l,&r);
			if(l==r)printf("0 ");
			else printf("%d ",query(1,1,n-1,l,r-1));
		}
		puts("");
	}
	return 0;
}

THE END

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...