P5881 【化学】实验 题解

发表于 分类于

本文迁移自洛谷原文。

自己的题，怎么能不写题解呢？

考察点：构图

我们可以新建$n$个点:$n+1 \dots2n$

第$i$个点表示$i-n$这个数

对于所有的$a_i$，将i与所有是$a_i$的约数的平方数的平方根所对应的节点号连一条边，权值为这个平方根

这样就可以转换成一个图论问题了！

也就是说，对于这张图，选出最大数量的点，使得两两之间不能由权值大于$x$的边相连。

我们很容易就可以发现， 在一个由权值大于$x$所组成的联通快中，最多只能选择一个。

所以跑$n$边dfs就可以了！

注意点1:

由于有$2 \times 10^5$个点和询问，所以裸的$O(nm)$是过不了的

通过打表可以发现，有很大一部分询问的答案是相同的

最多只需要查找$\sqrt{max{a_i}}=200$次即可。

所以只需要找到这个临界值就可以了

2.如何O($b_i^{\frac{1}{3}}$)求出$c_i$?

1
2
3
4
5
6
7
8
9
10
11
res=1;i=1
while i*i*i<=b[i]:
	cnt=0
	while b[i]%i==0:
		cnt=cnt+1
		b[i]=b[i]/i
	res=max(res,cnt)
last_b=b[i]
tmp=sqrt(b[i])
if tmp*tmp==b[i]:res=max(res,2)
return res

为什么这段代码是正确的？

假设 $last_b=p*q$

因为所有$\le b_i^{\frac{1}{3}}$的 因数都已经被while除完了

所以$p,q$一定为两个挺大的，互质的数

所以只要特判一下$p,q$是否相等即可

std:

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
#include<bits/stdc++.h>
#define mp make_pair
#define ll long long
using namespace std;
const int mxn=1000005;//real: 200000
int n,m;
int a[mxn],b[mxn],c[mxn];
vector<int>g[mxn];
int overban,t_o,mx;
bool use[mxn];
inline void dfs(int x){
	if(use[x])return;
	use[x]=1;
	if(x<=n)mx=max(mx,c[x]);
	for(int it=0;it<g[x].size();++it){
		int y=g[x][it];
		int ma=max(x,y);
		if(ma<=overban)continue;
		dfs(y);
	}
}
inline pair<int,int> solve(int xx){
	overban=xx;
	t_o=xx-n;
	int res=0,cnt=0;
	memset(use,0,sizeof(use));
	for(int i=1;i<=n;++i){
		if(!use[i]){
			mx=0;
			dfs(i);
			if(mx)++cnt;
			res+=mx;
		}
	}
	return mp(cnt,res);
}
pair<int,int>ans[mxn];
int main(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=n;++i){
		scanf("%d",a+i);
		for(int x=2;x*x<=a[i];++x){
			if(a[i]%(x*x)==0){
				g[i].push_back(n+x);
				g[n+x].push_back(i);
			}
		}
	}
	for(int i=1;i<=n;++i){   //b[i]^(1/3) calc c[i]
		scanf("%d",b+i);
		int t=b[i],res=1;
		for(int x=2;x*x*x<=t;++x){
			int c=0;
			for(;t%x==0;t/=x)++c;
			res=max(res,c);
		}
		int t2=sqrt(t);
		if(t2*t2==t)res=max(res,2);
		else res=max(res,1);
		c[i]=res;
	}
	for(int i=1;i<=200000;++i){
	    if(ans[i-1].first==n){
	        ans[i]=ans[i-1];
	        continue;
	    }
	    ans[i]=solve(i+n);
	}
	for(int i=1;i<=m;++i){
		int x;scanf("%d",&x);
		printf("%d %d\n",ans[x].first,ans[x].second);
	}
	return 0;
}