专栏文章

CF2005D Alter the GCD 题解

hhuangleyi0129暴力出奇迹
CF2005D题解参与者 1已保存评论 0

文章操作

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

当前评论
0 条
当前快照
1 份
快照标识符
@miqcls48
此快照首次捕获于
2025/12/04 02:36
3 个月前
此快照最后确认于
2025/12/04 02:36
3 个月前
查看原文
有如下经典结论：设 gig_i 为 aia_i 的前/后缀 gcd⁡\gcd ，则 gig_i 的取值只有 O(log⁡V)O(\log V) 种。
考虑 ll 从右向左做扫描线。
设：
gai=gcd⁡(al,⋯ ,ai),gbi=gcd⁡(bl,⋯ ,bi)ga_i=\gcd(a_l,\cdots,a_i),gb_i=\gcd(b_l,\cdots,b_i)
fai=gcd⁡(ai+1,⋯ ,an),fbi=gcd⁡(bi+1,⋯ ,bn)fa_i=\gcd(a_{i+1},\cdots,a_n),fb_i=\gcd(b_{i+1},\cdots,b_n)
动态维护 gai,gbiga_i,gb_i 和本质不同的数对 (gai,gbi,fai,fbi)(ga_i,gb_i,fa_i,fb_i)。
显然只有 O(log⁡V)O(\log V) 对。
且是一个不断单点删除，前缀加数的过程。
使用链表维护，时间复杂度 O(nlog⁡2V)O(n\log^2V)。
代码如下：
CPP
#include<bits/stdc++.h>
using namespace std;
const int N=200005;
int a[N],b[N],R[N],qa[N],qb[N],ga[N],fa[N],gb[N],fb[N],n,ans;
long long cnt;
void solve()
{
	ans=cnt=0;
	cin>>n;
	for(int i=1;i<=n;++i)
		cin>>a[i],qa[i]=__gcd(qa[i-1],a[i]),ga[i]=gb[i]=0,R[i]=i+1;
	for(int i=1;i<=n;++i)
		cin>>b[i],qb[i]=__gcd(qb[i-1],b[i]);
	int it,pre,u;
	a[n+1]=b[n+1]=fa[n+1]=fb[n+1]=0;
	for(int i=n;i>=1;--i)
	{
		it=i;
		fa[i]=__gcd(fa[i+1],a[i+1]),fb[i]=__gcd(fb[i+1],b[i+1]);
		while(it<=n)
			ga[it]=__gcd(ga[it],a[i]),gb[it]=__gcd(gb[it],b[i]),it=R[it];
		it=i+1,pre=i;
		while(it<n)
		{
			if(ga[it]==ga[R[it]]&&gb[it]==gb[R[it]]&&fa[it]==fa[R[it]]&&fb[it]==fb[R[it]])
				R[pre]=R[it],it=pre;
			pre=it,it=R[it];
		}
		pre=i-1,it=i;
		while(it<=n)
		{
			u=__gcd(qa[i-1],__gcd(gb[it],fa[it]))+__gcd(qb[i-1],__gcd(ga[it],fb[it]));
			if(u>ans)
				ans=u,cnt=it-pre;
			else if(u==ans)
				cnt+=it-pre;
			pre=it,it=R[it];
		}
	}
	cout<<ans<<' '<<cnt<<'\n';
}
int main()
{
	ios::sync_with_stdio(0),cin.tie(0);
	int T;
	cin>>T;
	while(T--)
		solve();
	return 0;
}

评论

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

正在加载评论...