GCD-counting在这千（ling）钧（ren）一（tou）发（da）的时刻，lzw大佬出现了！！！

87 阅读 0 评论 58 点赞

我是靠谱客的博主无语樱桃，最近开发中收集的这篇文章主要介绍GCD-counting在这千（ling）钧（ren）一（tou）发（da）的时刻，lzw大佬出现了！！！，觉得挺不错的，现在分享给大家，希望可以做个参考。

概述

这是一道CF压轴题，作为蒟蒻我不会..

好在有zju的lzw 巨佬，稍微懂了点就ac了。

简述一下题意：

题目给定一颗树（保证联通），每个点上附有全职并且可能相同。要求求出任意两点之间路径上的gcd出现的次数，如果有则输出gcd的值和相应次数。
数据量：点的个数给在 2x10^5 的范围，单点的值也是在2x10^5之间。

我最开始的思路

很明显，如果纯暴力求gcd暴力枚举，外在循环的复杂程度就达到了 n2 n 2 ，而内在的gcd又需要大量时间（而且有可能会爆栈）所以果断的放弃这一个想法。
考虑剪枝：如果两点之间的路径上存在的gcd为1，那么就不需要在这两条进行搜索，因为其他的值都是1。但是如果出现果断暴力数据（比如说退化成一条链，链上的值都是200000或者公约数是2，那么这个剪纸完全没什么用）。
继续深入（在错误的路上越走越远orz）考虑类似于LCA的作法发掘树的一些性质，最终——未果（orz看样子我注定爆零）

在这千（ling）钧（ren）一（tou）发（da）的时刻，lzw大佬出现了！！！

给我发来了一段题解。大意如下：

首先求取路径上的gcd十分的不现实！这个小学生都知道。
那么就求取 g[i] g [ i ] 意为在树中 pair<u,v> p a i r < u , v > 路径gcd是i的倍数，而这里需要一个 f[i] f [ i ] 来进行一下下的过渡（其实可以只靠外循环解决gcd的问题）。 f[i] f [ i ] 意为在树中有多少对 pair<u,v> p a i r < u , v > 路径gcd刚好是 i i 。
从这里就可以推出
$f [i] = g [i] - f [i * 2] - f [i * 3] . . .$
题目当中要求求出所有存在的 f[i] f [ i ] 。

那么怎么去求 g[i] g [ i ] 。

首先我只需要找到点权值是 i i 的倍数的位置并且标记。如果他的父亲也是被标记的，那么 $g [i]$ 的值就增加1。
后来想想我好想有点不太对，怎么样让父亲的父亲（他的爷爷）和他如果也是符合 g[i] g [ i ] 的要求能够联通。
那么要用到并查集来进行维护。
如果对于每一个符合的 <x,fa[x]> < x , f a [ x ] > <script type="math/tex" id="MathJax-Element-2053"> </script>进行他们所属的集合的size相乘再加到 g[i] g [ i ] 当中（这里可以证明，对于父亲和自己的两个集合，所求出的就是集合当中任意两个点作头和尾相连所得的路径数量之和），而前面有标记所以不需要判断是否合法（前面枚举点权是否是i的倍数的时候就已经筛过了）。

然后再用上面的推论求出相应的 f[i] f [ i ] 就可以了。而且据说CF的评测机贼快，给4.5s的这个算法只要1s不到就解决了（lzw大佬真的巨）

其实上面说的有点抽象我自己第一遍看他的话也没看懂….所以直接来看代码比较好理解一些。
其实c++ 11 版在vector里可以用auto但联赛好像没到版本…..代码量有点啰嗦。

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<queue>
#include<cmath>
#include<vector>
#include <bits/stdc++.h>
using namespace std;
const int MAXN=200010;
int n;
int a[MAXN],fa[MAXN],father[MAXN];
long long size[MAXN],ans[MAXN];
vector <int> lis[MAXN],E[MAXN];
int find(int x){
if (x == father[x]) return x;
return father[x] = find(father[x]);
}
void dfs(int x,int pre){
int s=E[x].size();
for (int i=0;i<s;i++){
int y=E[x][i];
if (y==pre) continue;
fa[y]=x;
dfs(y,x);
}
}
int main(){
scanf("%d",&n);
for (int i=1;i<=n;i++){
scanf("%d",&a[i]);
lis[a[i]].push_back(i);//lis 所存的是值为a[i]的位置 
}
for (int i=1;i<n;i++){
int u,v;
scanf("%d%d",&u,&v);
E[u].push_back(v);//联通两条边。 
E[v].push_back(u);
}
dfs(1,-1);// build tree
for (int i=1;i<=200000;i++){
for (int j=i;j<=200000;j+=i){
ans[i]+=lis[j].size();//此时lis[j]的大小就是有多少个j,而j是i的倍数 
int s=lis[j].size();
for (int t=0;t<s;t++){
int x=lis[j][t];//对于当前所需要查询的点进行附值 
father[x]=x;//标记需要找到的点
size[x]=1;
}
}
for (int j=i;j<=200000;j+=i){
int s=lis[j].size();
for (int t=0;t<s;t++){
int x=lis[j][t];
if(x==1) continue;
if(father[fa[x]]==0) continue;//由于之前的附值,所以没有附值的父亲就不是i的倍数 直接过滤 
int a=find(x),b=find(fa[x]);
ans[i]+=size[a]*size[b];//可以确定两个集合之间的所得的答案个数
father[a]=b;
size[b]+=size[a];
}
}
for (int j=i;j<=200000;j+=i){//制零。 
int s=lis[j].size();
for (int t=0;t<s;t++){
int x=lis[j][t];
father[x]= 0;
size[x] = 0;
}
}
}
for (int i=200000;i>=1;i--){
for (int j=2*i;j<=200000;j+=i)
ans[i]-=ans[j];//递推求解
}
for (int i=1;i<=200000;++i)
if (ans[i]) printf("%d %I64dn",i,ans[i]);
}