CF809E Surprise me!

套路题

CF809E Surprise me!

求:

1n(n1)i=1nj=1nφ(ai×aj)dist(i,j)\frac{1}{n(n-1)}\sum_{i=1}^n\sum_{j=1}^n\varphi(a_i\times a_j)·dist(i,j)

有一说一感觉这题非常套路。。模版练习题

然后看了看其他题解感觉 dp 部分可以不用做得那么麻烦吧()

首先显然我们不管前面那个分数。然后发现式子里面有 φ(ai×aj)\varphi(a_i\times a_j) 这个不太好处理的东西。。思考一下,我们希望能够化成这样的形式:

i=1nj=1nAiAjdist(i,j)\sum_{i=1}^n \sum_{j=1}^n A_i A_j dist(i,j)

这个东西看起来就比较好树形 dp 求出来。于是考虑把 φ(aiaj)\varphi(a_ia_j) 拆成 φ(ai)φ(aj)\varphi(a_i)\varphi(a_j) 这个东西。我们考虑对于一个质数 pkp_k ,如果有 pkaip_k | a_i 那么这个在算 φ(ai)\varphi(a_i) 的时候就会乘上 (pk1)pkα1(p_k-1)p_k^{\alpha - 1} 次方。如果它不存在于 aja_j 中,那么它对 φ(aiaj)\varphi(a_ia_j) 的贡献仍然是 (pk1)pkα1(p_k-1)p_k^{\alpha - 1} ,没有区别。否则,假设它对 aja_j 贡献是 (pk1)pkβ1(p_k-1)p_k^{\beta-1} ,那么它对 φ(aiaj)\varphi(a_ia_j) 相比于 φ(ai)φ(aj)\varphi(a_i)\varphi(a_j) 就少贡献了 pkpk1\frac{p_k}{p_k-1}。形式化地说:

φ(aiaj)=φ(ai)φ(aj)pkgcd(ai,aj)pkpk1\varphi(a_ia_j) = \varphi(a_i)\varphi(a_j) \prod_{p_k|\gcd(a_i,a_j)} \frac{p_{k}}{p_k-1}

这里就有了一个结论

φ(ab)=φ(a)φ(b)dφ(d),d=gcd(a,b)\varphi(ab) = \frac{\varphi(a)\varphi(b)d}{\varphi(d)} ,d = \gcd(a,b)

我们设 t(x)=pkxpkpk1t(x) = \prod_{p_k|x} \frac{p_{k}}{p_k-1} ,也就是说要做的是

i=1nj=1nφ(ai)φ(aj)t(gcd(ai,aj))dis(i,j)i=1nj=1nφ(ai)φ(aj)dis(i,j)k=1n[gcd(ai,aj)=k]t(k)\sum_{i=1}^n \sum_{j=1}^n \varphi(a_i)\varphi(a_j) t(\gcd(a_i,a_j)) dis(i,j)\\\sum_{i=1}^n \sum_{j=1}^n \varphi(a_i)\varphi(a_j)dis(i,j) \sum_{k=1}^n [\gcd(a_i,a_j)=k] t(k)\\

kk 提到前面去,那么就是:

k=1nt(k)kaikaj[gcd(aik,ajk)=1]φ(ai)φ(aj)dis(i,j)\sum_{k=1}^nt(k)\sum_{k|a_i}\sum_{k|a_j} [\gcd(\frac {a_i}k ,\frac{a_j} k) = 1] \varphi(a_i)\varphi(a_j) dis(i,j)\\

于是我们设 F(k)F(k) 为所有 gcd(ai,aj)=k\gcd(a_i,a_j)=k(i,j)(i,j) 的答案。算出这个再乘上 t(k)t(k) 就是最后的答案了。

F(k)=kaikaj[gcd(aik,ajk)=1]φ(ai)φ(aj)dis(i,j)F(k) = \sum_{k|a_i} \sum_{k|a_j} [\gcd(\frac{a_i} k,\frac{a_j} k) = 1]\varphi(a_i)\varphi(a_j) dis(i,j)\\

莫反一下:

F(k)=kaikajφ(ai)φ(aj)dis(i,j)kdgcd(ai,aj)μ(d)F(k) = \sum_{k|a_i} \sum_{k|a_j} \varphi(a_i)\varphi(a_j) dis(i,j) \sum_{kd|\gcd(a_i,a_j)} \mu(d)

dd 放到前面枚举:

F(k)=d=1nμ(d)kdaikdajφ(ai)φ(aj)dis(i,j)F(k) = \sum_{d=1}^n \mu(d) \sum_{kd|a_i} \sum_{kd|a_j} \varphi(a_i) \varphi(a_j) dis(i,j)

然后经典换 TT

F(k)=kTμ(Tk)TaiTajφ(ai)φ(aj)dis(i,j)F(k) = \sum_{k|T} \mu(\frac T k)\sum_{T|a_i}\sum_{T|a_j} \varphi(a_i)\varphi(a_j)dis(i,j)

后面那个式子看起来比较好求,我们单独设 f(k)=kaikajφ(ai)φ(aj)d(i,j)f(k) = \sum_{k|a_i} \sum_{k|a_j} \varphi(a_i)\varphi(a_j) d(i,j) ,然后 FF 的式子就变成了:

F(k)=kTμ(Tk)f(k)F(k) = \sum_{k|T} \mu(\frac T k) f(k)

我们考虑 ff 怎么求,我们枚举 kk 并且枚举点权为 kk 的倍数的点,拖出来建棵虚树,然后问题就变成了:

i=1nj=1nφ(ai)φ(aj)dis(i,j)\sum_{i=1}^n \sum_{j=1}^n \varphi(a_i)\varphi(a_j)dis(i,j)

这个就是前面说的那个看起来很可做的东西。。我们 dfs 一次求出到 1 的 j=1nφ(aj)dis(i,j)\sum_{j=1}^n \varphi(a_j)dis(i,j) 然后再 dfs 的过程中维护这个值就好了。具体就是把这个值 减去子树的权值和,再加上这个子树外的权值和(因为外面的点 disdis 增加了一,里面的点 disdis 减少了1)。

求出 ff ,于是就做完了。最坏复杂度大概是 O(nd(n)log(n))O(n d(n)\log(n)) ?反正 CF 8s 很稳。

#include "iostream"
#include "algorithm"
#include "cstring"
#include "cstdio"
#include "cmath"
#include "vector"
#include "map"
#include "set"
#include "bitset"
#include "queue"
using namespace std;
#define MAXN 200006
//#define int long long
#define rep(i, a, b) for (int i = (a), i##end = (b); i <= i##end; ++i)
#define per(i, a, b) for (int i = (a), i##end = (b); i >= i##end; --i)
#define pii pair<int,int>
#define fi first
#define se second
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define vi vector<int>
#define all(x) (x).begin() , (x).end()
#define mem( a ) memset( a , 0 , sizeof a )
#define P 1000000007
typedef long long ll;
int n , m;
int A[MAXN];

int Pow( int x , int a ) {
    int ans = 1 , cur = x % P;
    while( a ) {
        if( a & 1 ) ans = 1ll * ans * cur % P;
        cur = 1ll * cur * cur % P , a >>= 1;
    }
    return ans;
}

int pri[MAXN] , en , phi[MAXN] , mu[MAXN] , poi[MAXN];
void sieve() {
    phi[1] = mu[1] = 1;
    for( int i = 2 ; i < MAXN ; ++ i ) {
        if( !pri[i] ) pri[++ en] = i , phi[i] = i - 1 , mu[i] = -1;
        for( int j = 1 ; j <= en && i * pri[j] < MAXN ; ++ j ) {
            pri[i * pri[j]] = 1;
            if( i % pri[j] == 0 ) { phi[i * pri[j]] = phi[i] * pri[j]; break; }
            phi[i * pri[j]] = phi[i] * ( pri[j] - 1 ) , mu[i * pri[j]] = -mu[i];
        }
    }
}

vector<int> G[MAXN];
int g[MAXN][19] , dep[MAXN] , dfn[MAXN] , R[MAXN] , bac[MAXN] , clo;
void dfs( int u , int fa ) {
    dfn[u] = ++ clo , bac[clo] = u;
    for( int v : G[u] ) if( v != fa ) {
            dep[v] = dep[u] + 1;
            g[v][0] = u;
            rep( k , 1 , 18 ) if( g[g[v][k-1]][k-1] ) g[v][k] = g[g[v][k-1]][k-1]; else break;
            dfs( v , u );
        }
    R[u] = clo;
}
int lca( int u , int v ) {
    if( dep[u] < dep[v] ) swap( u , v );
    if( dep[u] != dep[v] )
        per( k , 18 , 0 ) if( dep[g[u][k]] >= dep[v] ) u = g[u][k];
    if( u == v ) return u;
    per( k , 18 , 0 ) if( g[u][k] != g[v][k] ) u = g[u][k] , v = g[v][k];
    return g[u][0];
}

vector<int> p;

namespace faketree { // build faketree with nodes from p
    bool cmp(int a, int b) { return dfn[a] < dfn[b]; }
    vector<int> G[MAXN];
    int n;
    int stk[MAXN] , tp , rt;
    void build() {
        sort(all(p) , cmp);
        rep(i, 1, p.size() - 1) p.pb(lca(p[i], p[i - 1]));
        sort(all(p) , cmp);
        n = unique( all( p ) ) - p.begin();
        tp = 0;
        stk[0] = 0;
        rt = p[0];
        rep( i , 0 , n - 1 ) {
            while( tp && R[stk[tp]] < dfn[p[i]] ) -- tp; // cur chain (in stack) is already added
            G[stk[tp]].pb( p[i] ) , G[p[i]].pb( stk[tp] );
            stk[++ tp] = p[i];
        }
    }
    int cur , sz[MAXN] , re , vis[MAXN];
    void dfs1( int u , int fa ) {
        sz[u] = vis[u] * phi[A[u]] , ( cur += ( vis[u] * 1ll * ( dep[u] - dep[rt] ) * phi[A[u]] ) % P ) %= P;
        for( int v : G[u] ) if( v != fa ) {
                dfs1( v , u );
                ( sz[u] += sz[v] ) %= P;
            }
    }
    void dfs( int u , int fa ) {
        ( re += ( 1ll * vis[u] * cur * phi[A[u]] ) % P ) %= P;
        for( int v : G[u] ) if( v != fa ) {
                int del =  1ll * ( dep[v] - dep[u] ) * ( ( 1ll * sz[rt] - 2 * sz[v] ) % P + P ) % P;
                if( !u ) del = 0;
                ( cur += del ) %= P;
                dfs( v , u );
                ( cur += P - del ) %= P;
            }
    }
    int workit( ) {
        for( int x : p ) vis[x] = 1;
        build( );
        re = cur = 0; dep[0] = -1;
        dfs1( 0 , 0 );
        dfs( 0 , 0 );
        for( int x : p ) G[x].clear() , vis[x] = 0; G[0].clear();
        return re;
    }
}

vi fk[MAXN];
int f[MAXN];

void solve() {
    sieve();
    cin >> n;
    rep( i , 1 , n ) scanf("%d",&A[i]) , fk[A[i]].pb( i );
    int u , v;
    rep( i , 2 , n ) scanf("%d%d",&u,&v) , G[u].pb( v ) , G[v].pb( u );
    dep[1] = 1; dfs( 1 , 1 );
    rep( i , 1 , n ) {
        p.clear();
        for (int j = i; j <= n; j += i)
            for (int t : fk[j]) p.pb(t);
        f[i] = faketree::workit();
    }
//    rep( i , 1 , n ) printf("%d ",f[i]); puts("");
    rep( i , 1 , n )
        for( int j = i + i ; j <= n ; j += i ) ( f[i] += f[j] * mu[j / i] < 0 ? f[j] * mu[j / i] + P : f[j] * mu[j / i] ) %= P; // now f is F
//    rep( i , 1 , n ) printf("%d ",f[i]); puts("");
    rep( i , 1 , n ) poi[i] = 1;
    rep( i , 1 , en ) if( pri[i] <= n )
            for( int j = pri[i] ; j <= n ; j += pri[i] ) poi[j] = 1ll * poi[j] * Pow( pri[i] - 1 , P - 2 ) % P , poi[j] = 1ll * poi[j] * pri[i] % P;
    int ans = 0;
    rep( i , 1 , n )
        ( ans += 1ll * poi[i] * f[i] % P ) %= P;
    printf("%lld\n",1ll * ans * Pow( 1ll * n * ( n - 1 ) % P , P - 2 ) % P);
}

signed main() {
//    freopen("input","r",stdin);
//    freopen("fuckout","w",stdout);
//    int T;cin >> T;while( T-- ) solve();
    solve();
}
\