GCD Counting

Yorg / 2024-10-21 / 原文

算法

$\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 加一维)

树上两点间的问题, 通常可以拆分成一个点 $\rightarrow$ $LCA$ $\rightarrow$ 另一个点
因此方程只需要考虑以自己为根的链即可

代码

事实上两个方程可以同步转移

for(int i=1;i<=Cnt[u];i++){
  for(int j=1;j<=Cnt[v];j++){
    if(Fac[u][i]==Fac[v][j]){
        g[u][i]=Max(g[u][i],f[u][i]+f[v][j]);
        //这个地方，是在转移当前的 $f_{u,i}$ 之前。
        //此时 $f_{u,i}$ 已经代表了此前访问过的所有 u 的儿子中符合要求且最长的链
        //只需要与当前所转移的 f[v][j]求和即可  
						

        f[u][i]=Max(f[u][i],f[v][j]+1);
      }
    }
 }