算法
\(\mathcal{O}(n \log n)\) 算法, \(95pts\)
观察题目，发现题目要求我们求 \(\gcd\) 不等于 \(1\) 的一条最长链
考虑将每个数分解质因数
对于每一个 \(1 \sim k\) 中的质数, 将所有含有这个质因子的数加入一颗虚树, 求最长链即可, 经过尝试发现 \(k = 700\) 时即可通过
可以用并查集维护连通块加速搜索, 时间复杂度中的 \(\log n\) 就是小常数并查集
但是这样子无法顾及到公因数很大的情况, 可以用 \(\rm{map}\) 维护要处理的质因数, 然后再来计算
但是我不想写了
代码
#include <bits/stdc++.h>
#define int long long
const int MAXN = 2e5 + 20;
int n;
int Val[MAXN];
struct node
{
int to, next;
} Edge[MAXN << 1];
int head[MAXN];
int cnt = 0;
void init()
{
for (int i = 1; i <= n; i++)
{
head[i] = -1;
}
}
void addedge(int u, int v)
{
Edge[++cnt].to = v;
Edge[cnt].next = head[u];
head[u] = cnt;
}
int Prime[MAXN];
int Vis[MAXN];
int Prime_cnt = 0;
void Euler(int x)
{
memset(Vis, false, sizeof(Vis));
memset(Prime, 0, sizeof(Prime));
for (int i = 2; i <= x; i++)
{
if(!Vis[i])
Prime[++Prime_cnt] = i;
for (int j = 1; j <= Prime_cnt && i * Prime[j] <= x; j++)
{
Vis[i * Prime[j]] = true;
if(i % Prime[j])
break;
}
}
}
bool CanUse[MAXN];
bool vis[MAXN];
int dist[MAXN];
class Union_Set
{
private:
public:
int fa[MAXN];
void init()
{
for (int i = 1; i <= n; i++)
{
fa[i] = i;
}
}
int find(int x)
{
return fa[x] = (fa[x] == x) ? fa[x] : find(fa[x]);
}
void merge(int u, int v)
{
int fa_u = find(u);
int fa_v = find(v);
fa[fa_u] = fa_v;
}
} US;
void dfs1(int Now, int fa, int d)
{
dist[Now] = d;
vis[Now] = true;
for (int i = head[Now]; ~i; i = Edge[i].next)
{
int Nowto = Edge[i].to;
if (CanUse[Nowto] && Nowto != fa)
{
US.merge(Now, Nowto);
dfs1(Nowto, Now, d + 1);
}
}
}
std::vector<int> Conect[MAXN];
int Conect_cnt = 0;
int Map[MAXN];
int Find_Longest_Road()
{
memset(vis, false, sizeof(vis));
US.init();
for (int i = 1; i <= n; i++)
{
if (!vis[i] && CanUse[i])
{
dfs1(i, -1, 1);
}
}
memset(vis, false, sizeof(vis));
for (int i = 1; i <= Conect_cnt; i++)
{
Conect[i].clear();
}
Conect_cnt = 0;
for (int i = 1; i <= n; i++)
{
if(!CanUse[i]) continue;
if(!vis[US.find(i)])
{
vis[US.find(i)] = true;
Conect[++Conect_cnt].push_back(i);
Map[US.find(i)] = Conect_cnt;
}else{
Conect[Map[US.find(i)]].push_back(i);
}
}
int Ans = 0;
for (int i = 1; i <= Conect_cnt; i++)
{
int rt = 0;
for (int j = 0; j < Conect[i].size(); j++)
{
if(dist[rt] < dist[Conect[i][j]])
{
rt = Conect[i][j];
}
}
dfs1(rt, -1, 1);
for (int j = 0; j < Conect[i].size(); j++)
{
Ans = std::max(Ans, dist[Conect[i][j]]);
}
}
return Ans;
}
signed main()
{
freopen("counting2.in", "r", stdin);
//freopen("counting.out", "w", stdout);
/*读入 + 建树*/
scanf("%lld", &n);
for (int i = 1; i <= n; i++)
scanf("%lld", &Val[i]);
init();
for (int i = 1; i <= n - 1; i++)
{
int u, v;
scanf("%lld %lld", &u, &v);
addedge(u, v);
addedge(v, u);
}
/*质数筛*/
Euler(25);
int Ans = 0;
for (int i = 1; i <= Prime_cnt; i++)
{
int Now_Gcd = Prime[i];
for (int j = 1; j <= n; j++)
{
if(Val[j] % Now_Gcd == 0)
{
CanUse[j] = true;
}else{
CanUse[j] = false;
}
}
Ans = std::max(Ans, Find_Longest_Road());
}
for (int i = 1; i <= n; i++)
{
if(Val[i] != 1)
{
printf("%lld", Ans);
return 0;
}
}
printf("0");
return 0;
}
/*
3
2 3 4
1 2
2 3
1
*/
/*
3
2 3 4
1 3
2 3
2
*/
/*
3
1 1 1
1 2
2 3
0
*/
总结
看到 \(\gcd\) 就要想分解质因数, 可以枚举 \(\gcd\) 的值从而解决问题
每道题目不一定要用一次操作进行完, 可以按照统一逻辑进行多次操作
\(\mathcal{O}(n)\) 算法
观察到这道题很像 树形 dp
于是去学了一下
容易发现 \(2 \times 10^5\) 内含有最多不同质因数的数量不超过 \(10\), 想到对每个数求质因数, 然后进行对含有相同质因数的进行转移
之前的 \(\mathcal{O}(n \log n)\) 算法需要找连通块之类的, 常数也不小, 而这一次我们想办法只在原图上进行操作, 略去了分图的时间复杂度 (类似于 分层图 \(\rightarrow\) dp 加一维)