T1 GCD Counting (CF1101D)

· · 个人记录

T1 GCD Counting (CF1101D)

CF传送门

洛谷传送门

数据加强版(UOJ) 100w数据

数据加强版(洛谷) 200w数据

题意简述

给出一棵有n个节点的树，树有点权 a_i ，求树上最长的一条链满足：链上所有点的点权的 gcd>1．

注意一个点也可以构成一条链．

数据范围
1 \leq n \leq 2 \times 10^5 1 \leq a_i \leq 2 \times 10^5 1 \leq u,v \leq 2 \times n$ , $u \neq v
题解

思路

首先看清题意，会发现一条链上的点权 gcd>1 等价于 存在一个 k ，使对于任意链上的点i， k|a_i

于是乎就把难以处理的gcd转换成了简单的整除问题

从约数的角度考虑。假如我已经确定了一个 k ，那问题就变为了把树上所有权值能被k整除的点 点亮，再找最长的链

显然可以用树上dp轻松搞定

但约数个数明显也不少啊

所以不妨再退回来，一次解决所有k

再回到只观察一个点，发现它只能由与它不互质的儿子转移上来

那就只转移这些就行了

再回来考虑 k

如果 k 不是质数，即 k=x*y

显然 集合A{ i | k|a_i } \in 集合B{ i | x|a_i }

这样就好办了，分解质因数 **做法** 先把每个节点的质因数处理出来 $ 2 \times 3 \times 5 \times 7 \times 11 \times 13 < 200000 < 2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17

所以约数个数至多6个

用 f[N][7] 存储约数即可

用 dp[i][j] 表示以 i 为根，经过 i 的，都能被 j 整除的最长路径长度

转移时直接暴力枚举即可（因为至多也就6*6=36嘛）

注意这只是从下往上的一条路径，

所以还要边dp边更新答案

把约数个数看作常数就是 O(n)

注意事项

· 建双边别忘了开两倍大小（也就只有我犯了这个错吧）

· 预处理好像可以用筛加速

但是我懒所以直接打表（最大202ms）

不加速也可以吧4.5s耶

· 别忘了初始化dp数组（全为1）

· 别忘了特判 a_i=0 的情况，输出0

AC代码

#include<bits/stdc++.h>
using namespace std;
const int N=20000005;
int n,a[N],f[N][7],dp[N][7],ans=1;
int k[100]={0,2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97,101,103,107,
109,113,127,131,137,139,149,151,157,163,167,173,179,181,191,193,197,199,211,223,
227,229,233,239,241,251,257,263,269,271,277,281,283,293,307,311,313,317,331,337,
347,349,353,359,367,373,379,383,389,397,401,409,419,421,431,433,439,443};
//sqrt(200000)内的质数表，打表使我快乐yeah 
struct nod{
    int to,nxt;
}e[N*2];//双边！ 
int head[N],cnt;
void add(int u,int v){
    e[++cnt].to=v;
    e[cnt].nxt=head[u];
    head[u]=cnt;
}
void dfs(int o,int fa){
    for(int i=head[o];i;i=e[i].nxt){
        int v=e[i].to;
        if(v==fa) continue;
        dfs(v,o);
        for(int j=1;j<=f[o][0];j++)
            for(int k=1;k<=f[v][0];k++) 
                if(f[o][j]==f[v][k])
                    ans=max(ans,dp[o][j]+dp[v][k]),//先更新答案 
                    dp[o][j]=max(dp[o][j],dp[v][k]+1);//再更新dp 
    }
}
int main(){
    scanf("%d",&n);
    bool flag=1;
    for(int i=1;i<=n;i++){
        scanf("%d",&a[i]);
        if(a[i]!=1) flag=0;//特判 
    }
    for(int i=1;i<=n-1;i++){
        int u,v; scanf("%d%d",&u,&v);
        add(u,v),add(v,u);
    }
    if(flag) {printf("0");return 0;}//特判 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=86 && k[j]*k[j]<=a[i];j++)
            if(a[i]%k[j]==0){
                while(a[i]%k[j]==0) a[i]/=k[j];
                f[i][++f[i][0]]=k[j];
            }
    //判断每个数的能否被质数整除 
    for(int i=1;i<=n;i++)
        if(a[i]!=1)
            f[i][++f[i][0]]=a[i];
    //除完肯定只剩下sqrt(200000)外的质数了，直接搬下来 
    for(int i=1;i<=n;i++)
        for(int j=1;j<=f[i][0];j++)
            dp[i][j]=1;
    //初始化dp数组 
    dfs(1,0);
    printf("%d",ans);
}

时间测试

n=200000$ $150ms n=2000000$ $1000ms