整理的算法模板合集： ACM模板

点我看算法全家桶系列！！！

实际上是一个全新的精炼模板整合计划

---

Problem

给定一棵点带权无根树，对于每个 k ∈ [ 1 , 2 ⋅ 1 0 5 ] k\in[1,2\cdot 10^5] k∈[1,2⋅105]，求出有多少个无序点对 ( x , y ) (x,y) (x,y) 满足 x x x 到 y y y 的简单路径（链）上的所有节点的点权的 gcd ⁡ \gcd gcd 等于 k k k。（点对中的 x x x 可以等于 y y y，即单点也算作一个答案， ( x , y ) (x,y) (x,y) 与 ( y , x ) (y,x) (y,x) 算作两种方案）

1 ≤ n , a i ≤ 2 × 1 0 5 1\le n,a_i\le 2\times 10^5 1≤n,ai​≤2×105

Input

3
1 2 3
1 2
2 3

Output

1 4
2 1
3 1

Solution

定义树上 gcd ⁡ ( x , y ) \gcd(x,y) gcd(x,y) 表示 从点 x x x 到点 y y y 之间的简单路径（链）经过的所有点的点权的 gcd ⁡ \gcd gcd。

设 a n s = f ( k ) ans=f(k) ans=f(k) ，其中 f ( n ) f(n) f(n) 表示题目中想要求的树上所有 gcd ⁡ ( x , y ) = n \gcd(x,y)=n gcd(x,y)=n 的点对 ( x , y ) (x,y) (x,y) 的数量。显然有些难以下手，因为这里求的是 gcd ⁡ = n \gcd=n gcd=n，已经固定了，也就是说我们需要算出所有的 gcd ⁡ \gcd gcd，显然是 O ( n 2 ) O(n^2) O(n2) 的复杂度。

树上问题比较抽象，不能很简练的列举出数学公式，考虑 gcd ⁡ \gcd gcd 计数问题尝试直接使用莫比乌斯反演公式解决。我们构造函数 F ( n ) = ∑ n ∣ d f ( d ) F(n)=\sum\limits_{n\mid d}f(d) F(n)=n∣d∑​f(d)
显然 F ( n ) F(n) F(n) 的实际含义为 n ∣ gcd ⁡ ( x , y ) n\mid\gcd(x,y) n∣gcd(x,y) 的点对 ( x , y ) (x,y) (x,y) 的数量，即所有简单路径（链）的 gcd ⁡ ( x , y ) \gcd(x,y) gcd(x,y) 中有因子 n n n 的点对的数量。

此时根据莫比乌斯反演公式有：

f ( n ) = ∑ n ∣ d F ( d ) μ ( d n ) f(n)=\sum_{n\mid d}F(d)\mu(\dfrac{d}{n}) f(n)=n∣d∑​F(d)μ(nd​)

因此我们只需要计算 F ( i ) , i ∈ [ 1 , max ⁡ { a [ i ] } ] F(i),i\in[1,\max\{a[i]\}] F(i),i∈[1,max{a[i]}] ，然后 O ( n l o g n ) O(nlogn) O(nlogn) 卷积计算 f ( i ) f(i) f(i) 即可。（ gcd ⁡ ( x , y ) ≤ max ⁡ ( a [ i ] ) \gcd(x,y)\le \max(a[i]) gcd(x,y)≤max(a[i])）

因为 F ( n ) F(n) F(n) 的含义为所有简单路径（链）的 gcd ⁡ ( x , y ) \gcd(x,y) gcd(x,y) 中有因子 n n n 的点对的数量，所以我们可以从因子的角度出发，求出所有点权的因子，因为点对 ( x , y ) (x,y) (x,y) 中 x x x 可以等于 y y y，所以 F(因子)++ ，然后对于所有的因子建分层图，每次处理一个因子。

对于因子 x x x，我们将 n − 1 n-1 n−1 条边 ( u , v ) (u,v) (u,v) 中所有 gcd ⁡ ( a [ u ] , a [ v ] ) \gcd(a[u],a[v]) gcd(a[u],a[v]) 含有因子 x x x 的边一起构建成一个分层图里，则该分层图中的所有边均有因子 x x x，在建图连边的过程中，对于两条链（连通块） A , B A,B A,B，我们需要计算有多少个点对，所以可以用并查集维护每个连通块的点的个数 size，使用并查集将他们连起来的时候， F ( x ) F(x) F(x) 得到的新的贡献（新的点对）显然为 s i z e [ A ] × s i z e [ B ] size[A]\times size[B] size[A]×size[B]（ A A A 中每一个点均可在 B B B 中任意选择一个点凑成一个新的点对）。对于所有因子执行这一过程，我们就可以计算出所有的 F ( i ) F(i) F(i)。

最后分析一下复杂度： 1 ∼ 2 × 1 0 5 1\sim 2\times 10^5 1∼2×105 中约数最多仅有 160 160 160 个，即每条边最多会在 160 160 160 个分层图里出现，我们先对每条边分解因子然后构建分层图，然后再枚举分层图使用并查集建图，复杂度为 O ( n × max ⁡ { 160 , n } ) O(n\times \max\{160, \sqrt{n}\}) O(n×max{160,n ​})

Code

#include <bits/stdc++.h> 
using namespace std;
using ll = long long;
const int N = 2e5 + 7, M = 2e3 + 7;

int n, m, k, t;
int a[N];
int primes[N], cnt, mu[N];
bool vis[N];
int fa[N], siz[N];
ll f[N], F[N];
int u[N], v[N];
int maxx;
vector <int> c[N];

template <typename T> inline void read(T& t) {
    int f = 0, c = getchar(); t = 0; 
    while (!isdigit(c)) f |= c == '-', c = getchar();
    while (isdigit(c)) t = t * 10 + c - 48, c = getchar();
    if (f) t = -t;
} 

template <typename T> void print(T x) {
    if (x < 0) x = -x, putchar('-');
    if (x > 9) print(x / 10);
    putchar(x % 10 + 48);
} 

void init(int n)
{
    vis[1] = 1; 
    mu[1] = 1;
    for(int i = 1; i <= n; ++ i) {
        if(vis[i] == 0) {
            primes[ ++ cnt] = i;
            mu[i] = -1;
        }
        for(int j = 1; j <= cnt && i * primes[j] <= n; ++ j) {
            vis[i * primes[j]] = 1;
            if(i % primes[j] == 0) {
                mu[i * primes[j]] = 0;
                break;
            }
            mu[i * primes[j]] -= mu[i];
        }
    }
}

int Find(int x)
{
    if(fa[x] == x) return x;
    return fa[x] = Find(fa[x]);
}

void Union(int d, int x, int y)
{
    int fx = Find(x);
    int fy = Find(y);
    if(fx == fy) return ;
    F[d] += 1ll * siz[fx] * siz[fy];
    fa[fx] = fy;
    siz[fy] += siz[fx];
}

signed main()
{
    init(N - 7);
    read(n);
    for(int i = 1; i <= n; ++ i) {
        read(a[i]);
        maxx = max(maxx, a[i]);
        int x = a[i];
        for(int j = 1; j * j <= x; ++ j) {
            if(x % j == 0) {
                F[j] ++ ;
                if(j * j != x) F[x / j] ++ ;
            }
        } 
    }
    /*for(int i = 1; i <= 2e5; ++ i) {
        if(F[i]) cout << F[i] << endl;
    }*/
    for(int i = 1; i <= n - 1; ++ i) {
        int x, y;
        read(x), read(y); 
        u[i] = x, v[i] = y;
        int gcd = __gcd(a[x], a[y]);
        for(int j = 1; j * j <= gcd; ++ j) {
            if(gcd % j == 0) {
                c[j].push_back(i);
                if(j * j != gcd) 
                    c[gcd / j].push_back(i);
            }
        } 
    }
    
    int limit = 2e5;
    for(int i = 1; i <= limit; ++ i) {
        
        for(int j = 0; j < c[i].size(); ++ j) {
            fa[u[c[i][j]]] = u[c[i][j]];
            siz[u[c[i][j]]] = 1;
            fa[v[c[i][j]]] = v[c[i][j]];
            siz[v[c[i][j]]] = 1;
        }
        for(int j = 0; j < c[i].size(); ++ j) {
            Union(i, u[c[i][j]], v[c[i][j]]);
        }
    }
    
    for(int i = 1; i <= limit; ++ i) {
        for(int j = i; j <= limit; j += i) {
            f[i] += 1ll * F[j] * mu[j / i];
        } 
    } 
    for(int i = 1; i <= limit; ++ i) {
        if(f[i]) {
            print(i);
            putchar(' ');
            print(f[i]);
            puts("");
        }
    }
    return 0;
}