多校联测13 菜

题目大意

有一个长度为$n$的序列$a$，你每次可以选择$\gcd$不为一的两个数$a_i$和$a_{i+1}$，将两个数合并，其值为两个数的$\text{lcm}$，也就是删去$a_{i+1}$，再让$a_i=\text{lcm}(a_i,a_{i+1})$。

求是否可以进行若干次操作，使得序列$a$的长度变为$1$。如果可行，就输出$Yes$；否则，输出$No$。

$1\le n\le 10^5,1\le a_i\le 700$

题解

首先，我们要知道，能合并的就合并，并不存在合并一个会使其他原本能合并的变得不能合并。我们可以维护一个栈，枚举每个元素，将当前元素与栈顶元素求$\gcd$，如果$\gcd$不为$1$就取出栈顶元素并与当前元素合并，并继续判断接下来的栈顶元素与当前元素的$\gcd$是否为$1$，直到不为一或栈为空。最后看栈内元素是否为$1$即可。

但在合并的过程中$a_i$会很大，甚至连$int128$都可能存不下。而$700$以内的质数只有$125$个，我们可以用$bitset$来存$a_i$有哪些质因子。

虽然用了$bitset$，但还是要枚举每个$a_i$是否有每个质因数，所以时间复杂度为$O(np)$，其中$p$为$700$以内质数的个数，也就是$125$。

code

#include
using namespace std;
const int N=700;
int n,q1,a[100005],r[100005],z[705],p[705],q[100005];
bitset<130>v[100005];
void init(){
	for(int i=2;i<=N;i++){
		if(!z[i]) p[++p[0]]=i;
		for(int j=1;j<=p[0]&&i*p[j]<=N;j++){
			z[i*p[j]]=1;
			if(i%p[j]==0) break;
		}
	}
}
int main()
{
	init();
	scanf("%d",&n);
	for(int i=1;i<=n;i++){
		scanf("%d",&a[i]);
		for(int j=1;a[i]>1&&j<=p[0];j++){
			if(a[i]%p[j]==0) v[i][j-1]=1;
			while(a[i]%p[j]==0) a[i]/=p[j];
		}
	}
	for(int i=1;i<=n;i++){
		q[++q1]=i;
		while(q1>=2&&(v[q[q1]]&v[q[q1-1]]).count()){
			v[q[q1-1]]|=v[q[q1]];
			--q1;
		}
	}
	if(q1==1) printf("Yes");
	else printf("No");
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36