Codeforece 990G. GCD Counting(点分治+暴力)

题目链接：G. GCD Counting

题意：

给定一个$n$个节点的带权树，求所有点对$(x,y)$间简单路径的$gcd$值，输出每种$gcd$的数量

题解：

考虑点分治，主体部分套板子就行，$solve$函数部分我们暴力，因为点分治$solve$的本质是考虑经过该点路径的贡献，显然经过该点的简单路径的$gcd$一定为该点权值的因子,因为权值$a\leqq 2e5$，所以在实际查找时经过该点形成的$gcd$的类型是很少的，我们可以直接用$map$储存下暴力求解,对应每个节点我们先记录根节点的权值到$mp$中，每次搜索子树，将形成的$gcd$放入到另一个$smp$中，这样每搜完一个子树后暴力枚举组合情况即可，最后记得每次将当前子树形成的$gcd$加入$mp$,这样就保证了形成的路径的端点是在不同子树之间。
具体细节参考代码和注释（这题卡常www，忘初始化S=n被卡了好久才发现）

#include<iostream>
#include<stack>
#include<list>
#include<set>
#include<vector>
#include<algorithm>
#include<math.h>
#include<numeric>
#include<map>
#include<cstring>
#include<string>
#include<queue>
#include<iomanip>
#include<cmath>
#include<ctime>
#include<queue>
#include <bitset>
#include <fstream>
#include <algorithm>
#include <cmath>
#include <ctime>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#ifndef local
#define endl 'n'
#endif */
#define mkp make_pair
using namespace std;
using std::bitset;
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
const int inf=0x3f3f3f3f;
const ll MAXN=2e6+10;
const ll INF=1e18;
const ll N=2e5+100;
const ll mod=1e9+7;
const ll hash_p1=1610612741;
const ll hash_p2=805306457;
const ll hash_p3=402653189;
//-----------------------------------------------------------------------------------------------------------------*/
// ll head[MAXN],net[MAXN],to[MAXN],edge[MAXN]/*流量*/,cost[MAXN]//费用;
/*
void add(ll u,ll v,ll w,ll s){
to[++cnt]=v;net[cnt]=head[u];edge[cnt]=w;cost[cnt]=s;head[u]=cnt;
to[++cnt]=u;net[cnt]=head[v];edge[cnt]=0;cost[cnt]=-s;head[v]=cnt;
}
struct elemt{
int p,v;
};
-----------------------------------
求[1,MAXN]组合式和逆元
ll mi(ll a,ll b){
ll res=1;
while(b){
if(b%2){
res=res*a%mod;
}
a=a*a%mod;
b/=2;
}
return res;
}
ll fac[MAXN+10],inv[MAXN+10];
void init(){
fac[0]=1;inv[0]=1;
for(ll i=1;i<=MAXN;i++){
fac[i]=(fac[i-1]*i)%mod;
inv[i]=mi(fac[i],mod-2);
}
}
ll C(int m,int n){//组合式C(m,n);
if(!n){
return 1;
}
if(m<n){
return 0;
}
return fac[m]*(inv[n]*inv[m-n]%mod)%mod;
}
ll lucas(int m,int n){//求C(m,n).一般用于m，n很大而mod很小，或者n，m不大但大于mod的情况(一般为mod不确定时用)
return n?C(m%mod,n%mod)*lucas(m/mod,n/mod)%mod:1;
}
---------------------------------
unordered_map<int,int>mp;
struct comp{
public:
bool operator()(elemt v1,elemt v2){
return v1.v<v2.v;
}
};
//优先队列默认小顶堆 ， greater<int> --小顶堆
less<int> --大顶堆
priority_queue<elemt,vector<elemt>,comp>q;
set<int>::iterator it=st.begin();
*/
//push_back()
等于push_back(),但效率更高,传输pair时push_back(i,j)==push_back({i,j}) 
// vector<vector<int>>edge; 二维虚拟储存坐标 
//-----------------------------------------------------------------------------------------------------------------*/
//mt19937 rnd(time(0));//高质量随机化函数，直接调用rnd()即可
//map<int,bool>mp[N]; 
//map<int,int>::iterator it;//迭代器
//push_back() 
/*
int dx[4]={0,0,1,-1};
int dy[4]={1,-1,0,0};
*/
struct elemt{//结构体存边
int v,w;
};
vector<elemt>e[N];//存边
int sz[N];//点i子树大小
int root;//当前重心
int MX;//当前重心对应最大子树大小
int S;//当前树大小
int mxson[N];//当前节点最大子树大小
bool vis[N];//当前点是否分治过
int n,k;
inline void read(int &hy) //快读
{
hy=0;
char cc=getchar();
while(cc<'0'||cc>'9')
cc=getchar();
while(cc>='0'&&cc<='9')
{
hy=(hy<<3)+(hy<<1)+cc-'0';
cc=getchar();
}
}
inline void add(int u,int v,int w){//建边（双向）
elemt tmp;
tmp.v=v;
tmp.w=w;
e[u].push_back(tmp);
tmp.v=u;
e[v].push_back(tmp);
}
inline void get_root(int x,int pre){//获取当前子树重心(存到root中)
sz[x]=1;mxson[x]=0;
for(int i=0;i<e[x].size();i++){
elemt tmp=e[x][i];
if(vis[tmp.v]||tmp.v==pre){
continue;
}
get_root(tmp.v,x);
sz[x]+=sz[tmp.v];
mxson[x]=max(mxson[x],sz[tmp.v]);
}
mxson[x]=max(mxson[x],S-sz[x]);
if(mxson[x]<MX){
root=x;
MX=mxson[x];
}
}
//-----------------------------根据不同题目确定
int a[N];
ll ans[N];//储存答案
int gcd(int a,int b){
return a%b==0?b:gcd(b,a%b);
}
map<int,int>mp,smp;//分别储存当前已经有的gcd组合和子树新产生的集合对应数量
map<int,int>::iterator itx,ity;//迭代器
inline void get_dis(int x,int pre,int gd){//更新当前子树中能产生的gcd值
smp[gd]++;
for(int i=0;i<e[x].size();i++){
int tmp=e[x][i].v;
if(vis[tmp]||tmp==pre){
continue;
}
get_dis(tmp,x,gcd(a[tmp],gd));
}
}
inline void solve(int x){
mp.clear();
mp[a[x]]++;
ans[a[x]]++;//pair(x,x)的情况
for(int i=0;i<e[x].size();i++){
int tmp=e[x][i].v;
if(vis[tmp]){
continue;
}
smp.clear();
get_dis(tmp,x,gcd(a[x],a[tmp]));
//因为经过x的所有路径的gcd一定为x的因子，所以类型会非常少，直接暴力枚举
for(itx=mp.begin();itx!=mp.end();itx++){//暴力枚举所有组合情况
for(ity=smp.begin();ity!=smp.end();ity++){
int gds=gcd((*itx).first,(*ity).first);
ans[gds]+=(ll)(*itx).second*(*ity).second;
}
}
for(ity=smp.begin();ity!=smp.end();ity++){//把当前子树的情况更新带总的情况上去
mp[(*ity).first]+=(*ity).second;
}
}
}
//--------------------------------
inline void Divide(int x){//点分治
vis[x]=1;//标记当前点
//--------------------------
//这里的solve是点分治精髓，看具体题目确定
solve(x);
//------------------------
for(int i=0;i<e[x].size();i++){
elemt tmp=e[x][i];
if(vis[tmp.v]){
continue;
}
S=sz[tmp.v];root=0;MX=inf;//寻找子树重心作为新分治点
get_root(tmp.v,0);
Divide(root);
}
}
int main(){
/*cout<<setiosflags(ios::fixed)<<setprecision(8)<<ans<<endl;//输出ans（float）格式控制为8位小数（不含整数部分）*/
/*cout<<setprecision(8)<<ans<<endl;//输出ans（float）格式控制为8位小数（含整数部分）*/
//ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);//同步流
int n;
cin>>n;
for(int i=1;i<=n;i++){
read(a[i]);
}
for(int i=1;i<n;i++){
int u,v,w=0;
read(u);
read(v);
add(u,v,w);
}
S=n;//q
root=0;MX=inf;
get_root(1,0);//获取整棵树的重心作为初始点
Divide(root);
for(int i=1;i<=200000;i++){//输出答案
if(ans[i]){
cout<<i<<" "<<ans[i]<<endl;
}
}
return 0;
}

最后

以上就是饱满芒果最近收集整理的关于Codeforece 990G. GCD Counting(点分治+暴力)Codeforece 990G. GCD Counting(点分治+暴力)的全部内容，更多相关Codeforece内容请搜索靠谱客的其他文章。