首页 > 其他 > 详细

CF1101D GCD Counting

时间:2019-01-17 21:03:51      阅读:179      评论:0      收藏:0      [点我收藏+]

CF1101D GCD Counting 

又被trick了

不用什么点分治

直接树形dp即可

开始的想法:

f[x][j]x为根的子树gcd至少为j(j是x的一个约数)的最长链

然后对y合并。类似于树的直径

但是复杂度还是很大的。。。

 

这个题的关键是:我们只关心gcd是不是1,并不关心gcd是什么!

gcd不是1,意味着一定有公共质因子!

而质因子个数非常少

可以f[x][j]表示,x为根的子树,往下走,公共质因子为j的最长链

然后甚至可以暴力合并!

显然最优解可以被处理到!

 

代码:

#include<bits/stdc++.h>
#define reg register int
#define il inline
#define numb (ch^‘0‘)
using namespace std;
typedef long long ll;
il void rd(int &x){
    char ch;x=0;bool fl=false;
    while(!isdigit(ch=getchar()))(ch==-)&&(fl=true);
    for(x=numb;isdigit(ch=getchar());x=x*10+numb);
    (fl==true)&&(x=-x);
}
namespace Miracle{
const int N=2e5+5;
vector<int>p[N],f[N];
int n;
int ans;
struct node{
    int nxt,to;
}e[2*N];
int hd[N],cnt;
void add(int x,int y){
    e[++cnt].nxt=hd[x];
    e[cnt].to=y;
    hd[x]=cnt;
}
void dfs(int x,int fa){
    for(reg i=hd[x];i;i=e[i].nxt){
        int y=e[i].to;
        if(y==fa) continue;
        dfs(y,x);
        for(reg j=0;j<p[x].size();++j){
        //    cout<<" j "<<p[x][j]<<endl;
            for(reg k=0;k<p[y].size();++k){
            //    cout<<" k "<<p[y][k]<<endl;
                if(p[x][j]==p[y][k]){
                    ans=max(ans,f[x][j]+f[y][k]);
                    f[x][j]=max(f[x][j],f[y][k]+1);
                }
            }
        }
    }
}
void div(int x,int id){
    for(reg i=2;(ll)i*i<=x;++i){
        if(x%i==0){
            p[id].push_back(i);
            f[id].push_back(1);
            while(x%i==0) x/=i;
        }
    }
    if(x>1){
        p[id].push_back(x);
        f[id].push_back(1);
    }
}
int main(){
    rd(n);int x;
    bool flag=false;
    for(reg i=1;i<=n;++i){
        rd(x);
        if(x!=1) flag=true;
        div(x,i);
    }
    if(!flag){
        puts("0");return 0;
    }
    ans=1;
    int y;
    for(reg i=1;i<=n-1;++i){
        rd(x);rd(y);
        add(x,y);add(y,x);
    }
    dfs(1,0);
    printf("%d",ans);
    return 0;
}

}
signed main(){
    Miracle::main();
    return 0;
}

/*
   Author: *Miracle*
   Date: 2019/1/17 19:37:47
*/

总结:
其实有些时候,题目很麻烦

但是实际上可以简化条件,想想我们关心什么

CF1101D GCD Counting

原文:https://www.cnblogs.com/Miracevin/p/10284269.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!