寻找小竹!(DFS+素数筛变形筛不同质因数个数)

E-寻找小竹！_牛客小白月赛60 (nowcoder.com)

链接：登录—专业IT笔试面试备考平台_牛客网
来源：牛客网
 

妈妈发现小竹逃走了，非常的气愤，她决定出去寻找小竹！和小竹不同的是，妈妈是道路上行走。

妈妈和小竹所在的城市有 n 个路口，n−1条道路，并且保证任意两个路口互相联通。每个路口根据妈妈审美的不同都有一个优雅值，而如果两个相邻的路口的优雅值存在至少两个共同的质因子p和q(p!=q）则这两个相邻的路口就是共同优雅的。

妈妈将共同优雅联通块定义为：在城市中选取若干个路口，若这些路口们两两互相联通，且每两个相邻的路口都是共同优雅的，则该联通块称为共同优雅联通块。

注意：单独的一个路口也符合共同优雅联通块的定义。

妈妈想知道，整个城市的最大优雅联通块包含多少个路口。

输入描述:

第一行一个正整数n(1≤n≤106)n表示有 n个路口。

第二行 n个整数，第 i个整数为 i​(1≤ai​≤5×106) 表示该路口的优雅值。

接下来 n−1 行，每行两个整数 x,y(1≤x,y≤n) 表示 x路口到 y 路口有一条道路。

输出描述:

一行一个整数，表示最大优雅联通块包含多少个路口。

示例1

输入

4 12 12 4 18 1 2 1 3 2 4

4
12 12 4 18
1 2
1 3
2 4

输出

3

3

说明

最大优雅联通块为 1,2,4三个路口所在的联通块,两两相邻的路口均包含 2,3 两个质因子

题解:

对于这道题,和明显结构为一棵树,没有成环的地方,让我们找最大优雅连通块的数量,很明显相到DFS,把所有的边存进去后开始遍历,DFS每个点,每遇到一个,就记录一下,代表走过,看每个相邻的符不符合,因为边数只有n-1条,并且都只会走一遍,是肯定不会t的

但是这道题难点并不在,DFS上,真正难的是如何以常数级别的时间复杂度判断两个相邻的点是否优雅,这里可以利用素数筛的变形,提前筛出来,一个数有几个不同的质因数

这部分代码如下

void init()
{
    for(int i = 2;i <= 5000000;i++)
    {
        if(!f[i])
        {
            for(int j = i;j <= 5000000;j+=i)
            {
                cnt[j]++;
                f[j] = 1;
            }
        }
    }
}

cnt[j]代表大小为j的数,他的不同的质因数有几个,因为每次都是为质数的i进入内部循环,所以每次遍历的j一定有一个质因子为i

为什么我们知道这个就可以求两个数有多少个共同质因子了呢?

我们可以先求出两个数的最大公因数x,这个x肯定也包含这两个数的相同质因数在内,

所以我们只用看这个cnt[x]值是否大于2即可,就代表这两个数有至少两个不同的质因子

#include<iostream>
#include<map>
#include<algorithm>
#include<queue>
#include<vector>
#include<cstring>
#include<cmath>
using namespace std;
int n;
int a[1000060];
int vis[1000050];
vector<int> p[1000050];
int f[5000060];
int cnt[5000060];
int k = 0;
int dfs(int x)
{
	vis[x] = 1;
	int ans = 1;
	for(auto v:p[x])
	{
		if(!vis[v])
		{
			int b = __gcd(a[x],a[v]);
			if(cnt[b]>=2)
			{
				ans += dfs(v);
			}
		}
	}
	return ans;
}
void init()
{
	for(int i = 2;i <= 5000000;i++)
	{
		if(!f[i])
		{
			for(int j = i;j <= 5000000;j+=i)
			{
				cnt[j]++;
				f[j] = 1;
			}
		}
	}
}
int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0); 
	init();
	int n;
	cin >> n;
	for(int i = 1;i <= n;i++)
	cin >> a[i];
	for(int i =1;i < n;i++)
	{
		int l,r;
		cin >> l >>r;
		p[l].push_back(r);
		p[r].push_back(l);
	}
	int ma = 0;
	for(int i = 1;i <= n;i++)
	{
		if(!vis[i])
		{
			ma = max(dfs(i),ma);
		}
	}
//	for(int i =1;i <= 100;i++)
//	cout<<cnt[i]<<"\n";
	cout<<ma;
}
//dp[i]    dp[i-1-k] + a[i]  dp[i - 1]