专栏文章

题解：CF2126E G-C-D, Unlucky!

xxxxalq
CF2126E题解参与者 3已保存评论 2

文章操作

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

当前评论
2 条
当前快照
1 份
快照标识符
@miors7ke
此快照首次捕获于
2025/12/03 00:05
3 个月前
此快照最后确认于
2025/12/03 00:05
3 个月前
查看原文
洛谷题目链接 & CF 题目链接

思路分析

观察分析一些性质。
一个序列的前缀或后缀的 gcd⁡\gcd，lcm⁡\operatorname{lcm}，max⁡\max，min⁡\min 都具有单调性，其中 gcd⁡\gcd 和 min⁡\min 单调不增，lcm⁡\operatorname{lcm} 和 max⁡\max 单调不降。
对于任意一个前缀 gcd⁡\gcd 记为 g1,g2,…,gkg_1,g_2,\dots,g_k 有以下性质，后缀同理。g1=a1g_1=a_1，这个显然。然后就是 gi+1∣gig_{i+1}|g_i，因为有递推式 gi+1=gcd⁡(gi,ai+1)g_{i+1}=\gcd(g_i,a_{i+1})，所以 gi+1g_{i+1} 一定是 g1g_1 的因数。还有一个显然的性质是 gk=gcd⁡(a1,a2,…,ak)g_{k}=\gcd(a_1,a_2,\dots,a_k)，即最后一个位置的值是整个前缀的 gcd⁡\gcd。根据以上性质可以进行初步判定但是还没结束，随便构造几个样例就可以 hack 掉。
根据最后一条性质我们得到一些启发，在原题中 pn=s1=gcd⁡(a1,a2,…,an)p_n=s_1=\gcd(a_1,a_2,\dots,a_n)，进一步考虑，pi=gcd(a1,a2,…,ai)p_i=gcd(a_1,a_2,\dots,a_i)，si+1=gcd⁡(ai+1,ai+2,…,an)s_{i+1}=\gcd(a_{i+1},a_{i+2},\dots,a_n)。那么 gcd⁡(pi,si+1)\gcd(p_i,s_{i+1}) 就应该等于整个序列的 gcd⁡\gcd 也就是 pnp_n 和 s1s_1。
然后这个题就做完了。

赛时代码

CPP
//code by xxxalq
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int maxn=100003;

int read(){
	int x=0,f=1;
	char ch=getchar();
	while(ch>57||ch<48){
		if(ch==45){
			f=-1;
		}
		ch=getchar();
	}
	while(ch>=48&&ch<=57){
		x=(x<<1)+(x<<3)+(ch-48);
		ch=getchar();
	}
	return x*f;
}

int gcd(int a,int b){
	if(b==0){
		return a;
	}
	return gcd(b,a%b);
}

int T,n,a[maxn],b[maxn];

bool solve(){
	if(a[n]!=b[1]){
		return false;
	}
	for(int i=1;i<n;i++){
		if(a[i]%a[i+1]||b[i+1]%b[i]){
			return false;
		}
		if(gcd(a[i],b[i+1])!=a[n]){
			return false;
		}
	}
	return true;
}

int main(){
	T=read();
	while(T--){
		n=read();
		for(int i=1;i<=n;i++){
			a[i]=read();
		}
		for(int i=1;i<=n;i++){
			b[i]=read();
		}
		if(n==1&&a[1]==b[1]){
			cout<<"YES\n";
			continue;
		}
//		cout<<T<<'\n';
//		if(n==2){
//			if(a[1]%a[2]==0&&b[2]%b[1]==0&&a[1]==b[2]&&a[2]==b[1]){
//				cout<<"YES\n";
//			}else{
//				cout<<"NO\n";
//			}
//			continue;
//		}
		cout<<(solve()?"YES":"NO")<<'\n';
	}
	return 0;
}

评论

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

正在加载评论...