OI - GCD Counting(Codeforces) | Lucky_Glass's Blog

以心为名，名为爱惜

0%

OI - GCD Counting(Codeforces)

发表于 分类于 Valine：

其实给自己立了一个一周5*Blog的小flag awa

# 题面

点击展开/折叠题面

给出一棵树，树有点权，求树上的一条链满足：链上所有点的点权的 $gcd>1$ 且链上的点数最多（注意一个点也可以构成一条链），求链长。

# 解析

首先我们知道一个数 $a$ 的质因数数量的不严格上界为 $\log_2 a$（实际上去重之后远比这个值小）。

一条链的 $gcd>1$ 即这条链上所有点有至少一个公共质因子，于是可以想到对每个可能出现的质因子单独建图（如质因子 $x$ 建出的图中只含被 $x$ 整除的点）。

这样建出来的图显然是一个森林，对于森林中的每棵树，找它的直径，可以树形DP也可以DFS两遍（因为是树形DP练习所以我写了树形DP）。

接下来就是一些小技巧了。

上面算法的复杂度是 $O(n\log n)$ 的，我们不希望在建图的时候破坏这个复杂度。于是我们不能 $O(n\sqrt n)$ 来质因数分解，这时候就会马上联想到线性筛（反正我就直接想到了）——每个数会被其最小质因子筛去。

于是线性筛的时候我们储存每个数是被哪个数筛去，记为 fli[i]，要质因数分解，就可以下面这样：

当然你也可以直接在这里就去重，详见代码。

> Tab. 接下来定义 $P_i$ 是点 $i$ 的质因数集合

然后怎么建图？有用的点只有 $O(n\log n)$……虚树？呸和LCA又没有什么关系为什么要虚树 awa

在原图中的边 $(u,v)$，对于每个质因子 $x\in P_u\cap P_v$，把边 $(u,v)$ 建在质因子 $x$ 的子图中。

怎样找 $x\in P_u\cap P_v$？注意到之前的 $\textbf{Split}(x)$ 函数其实是从小到大找到的质因子，因此 $P_u,P_v$ 是天然有序的，所以 two-point 扫一扫就好啦~

# 源代码

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
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
/*Lucky_Glass*/
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;

const int N=2e5+10,S=N*11;

int n,npid,ans;
int prn[N],fli[N],nprn;
int dvv[N][11],pid[N][11];
bool vis[S];
int f[S][2],ef[S][2];

struct GRAPH{
	int head[S],nxt[S<<1],to[S<<1],ncnt;
	void AddEdge(int u,int v){
		int p=++ncnt,q=++ncnt;
		nxt[p]=head[u],to[p]=v,head[u]=p;
		nxt[q]=head[v],to[q]=u,head[v]=q;
	}
	int operator [](const int &u){return head[u];}
}Gr;

void Prepare(){
	memset(f,-1,sizeof f);
	memset(ef,-1,sizeof ef);
	for(int i=2;i<N;i++){
		if(!fli[i]) fli[i]=i,prn[++nprn]=i;
		for(int j=1;j<=nprn && prn[j]*i<N;j++){
			fli[prn[j]*i]=prn[j];
			if(i%prn[j]==0) break;
		}
	}
}
inline int Ri(){
	register int r=0,c=getchar();
	while(c<'0' || '9'<c) c=getchar();
	while('0'<=c && c<='9') r=(r<<1)+(r<<3)+c-'0',c=getchar();
	return r;
}
void DP1(int u,int fa){
	vis[u]=true;
	f[u][0]=0;
	for(int it=Gr[u];it;it=Gr.nxt[it]){
		int v=Gr.to[it];
		if(v==fa) continue;
		DP1(v,u);
		int upd=f[v][0]+1;
		if(f[u][0]<upd) f[u][1]=f[u][0],ef[u][1]=ef[u][0],f[u][0]=upd,ef[u][0]=v;
		else if(f[u][1]<upd) f[u][1]=upd,ef[u][1]=v;
	}
	ans=max(ans,f[u][0]);
	ans=max(ans,f[u][0]+f[u][1]);
}
void DP2(int u,int fa,int g){
	ans=max(ans,max(g+1,g+f[u][0]+1));
	for(int it=Gr[u];it;it=Gr.nxt[it]){
		int v=Gr.to[it];
		if(v==fa) continue;
		if(v==ef[u][0]) DP2(v,u,max(g+1,f[u][1]+1));
		else DP2(v,u,max(g+1,f[u][0]+1));
	}
}
int main(){
	Prepare();
	n=Ri();
	for(int i=1;i<=n;i++){
		int val=Ri(),las=-1;
		while(val>1){
			if(las!=fli[val]){
				dvv[i][++dvv[i][0]]=las=fli[val];
				pid[i][dvv[i][0]]=++npid;
			}
			val/=fli[val];
		}
	}
	for(int i=1;i<n;i++){
		int u=Ri(),v=Ri();
		int p1=1,p2=1;
		while(p1<=dvv[u][0] && p2<=dvv[v][0]){
			if(dvv[u][p1]<dvv[v][p2]) p1++;
			else if(dvv[u][p1]>dvv[v][p2]) p2++;
			else Gr.AddEdge(pid[u][p1],pid[v][p2]),p1++,p2++;
		}
	}
	for(int i=1;i<=npid;i++)
		if(!vis[i])
			DP1(i,0),DP2(i,0,0);
	printf("%d\n",ans);
	return 0;
}

THE END

Thanks for reading!

> Linked 横竖撇点折-网易云