Codeforces 809E. Surprise me!

给一棵树，每个点点权 $a_i$，保证 $a_i$ 各不相同，现在随机选两个点 $u,v$，求 $f(u,v)=\varphi(a_u\cdot a_v)\cdot dis(u,v)$ 的期望，$\bmod 10^9+7$。

链接：http://codeforces.com/contest/809/problem/E

Solution

首先，有一个结论：$\varphi(a\cdot b)=\frac{\varphi(a)\cdot\varphi(b)\cdot g}{\varphi(g)},g=\gcd(a,b)$。
证明：考虑找一个 $x$，使得 $x|b,\gcd(\frac{b}{x},a)=1,\gcd(x,\frac{b}{x})=1$ 且 $a$ 包含 $x$ 中所有质因子。
那么 $\varphi(a\cdot b)=\varphi(a)\cdot x\cdot\varphi(\frac{b}{x})=\frac{\varphi(a)\cdot\varphi(b)\cdot x}{\varphi(x)}$。
显然，$x$ 是 $g$ 的倍数，所以 $\frac{x}{g}=\frac{\varphi(x)}{\varphi(g)}$，所以 $\varphi(a\cdot b)=\frac{\varphi(a)\cdot\varphi(b)\cdot g}{\varphi(g)}$。

有了这个结论之后可以考虑点分，那么设 $dis(x)$ 表示 $x$ 到当前根的距离。
设 $h(x)=\frac{x}{\varphi(x)}$，那么 $f(u,v)=\varphi(a_u)\cdot\varphi(a_v)\cdot h(g)\cdot(dis(u)+dis(v)),g=\gcd(a_u,a_v)$。
考虑当 $u$ 确定时，需要知道 $\sum\varphi(a_v)\cdot h(\gcd(a_u,a_v))$ 和 $\sum\varphi(a_v)\cdot h(gcd(a_u,a_v))\cdot dis(v)$。
设 $g(x)=h(x)-\sum[y|x,y\neq x]g(y)$，那么 $h(\gcd(a_u,a_v))=\sum[x|a_u,x|a_v]g(x)$。
这样就可以直接枚举约数算贡献了。

Code

#include<bits/stdc++.h>
typedef long long ll;
inline void repr(int&a,int b){if(a<b)a=b;}
#define mset(a,b) memset(a,b,sizeof(a))
#define fo0(i,n) for(int i=0,i##end=n;i<i##end;i++)
#define fo1(i,n) for(int i=1,i##end=n;i<=i##end;i++)
#define fo(i,a,b) for(int i=a,i##end=b;i<=i##end;i++)
#define foe(i,x)for(__typeof(x.end())i=x.begin();i!=x.end();++i)

const int N=200007,P=1000000007;

struct edge
{
    int to;edge*ne;
}_e[N*2],*e=_e,*p[N];

inline void add(int a,int b)
{
    *e=(edge){b,p[a]};p[a]=e++;
}

std::vector<int>v[N];
int n,pr[N],pm,phi[N],inv[N],f[N],w[N],sz[N],rsz,nro,nsz,g[N],h[N],q[N],qe,ans;
bool vis[N];

inline void dfs1(int x,int fa)
{
    sz[x]=1;
    for(edge*i=p[x];i;i=i->ne)
        if(i->to!=fa&&!vis[i->to])
        {
            dfs1(i->to,x);
            sz[x]+=sz[i->to];
        }
}

inline void dfs2(int x,int fa)
{
    int t=rsz-sz[x];
    for(edge*i=p[x];i;i=i->ne)
        if(i->to!=fa&&!vis[i->to])
        {
            repr(t,sz[i->to]);
            dfs2(i->to,x);
        }
    if(t<nsz)nsz=t,nro=x;
}

inline void set(int x,int y,int z)
{
    if(!~g[x])q[qe++]=x,g[x]=h[x]=0;
    g[x]=(g[x]+(ll)y*f[x])%P;
    h[x]=(h[x]+(ll)z*f[x])%P;
}

inline void get(int x,int&y,int&z)
{
    if(~g[x])y=g[x],z=h[x];
    else y=z=0;
}

inline void dfs3(int x,int fa,int dis)
{
    int a=phi[w[x]],b=(ll)a*dis%P;
    foe(i,v[w[x]])set(*i,a,b);
    for(edge*i=p[x];i;i=i->ne)
        if(i->to!=fa&&!vis[i->to])
            dfs3(i->to,x,dis+1);
}

inline void dfs4(int x,int fa,int dis)
{
    int a=phi[w[x]],b=(ll)a*dis%P,A,B;
    foe(i,v[w[x]])
    {
        get(*i,A,B);
        ans=(ans+(ll)a*B+(ll)b*A)%P;
    }
    for(edge*i=p[x];i;i=i->ne)
        if(i->to!=fa&&!vis[i->to])
            dfs4(i->to,x,dis+1);
}

inline void work(int x)
{
    dfs1(x,0);
    rsz=nsz=sz[x],nro=x;
    dfs2(x,0);
    vis[x=nro]=1;
    foe(i,v[w[x]])set(*i,phi[w[x]],0);
    for(edge*i=p[x];i;i=i->ne)
        if(!vis[i->to])
        {
            dfs4(i->to,x,1);
            dfs3(i->to,x,1);
        }
    fo0(i,qe)g[q[i]]=h[q[i]]=-1;
    qe=0;
    for(edge*i=p[x];i;i=i->ne)
        if(!vis[i->to])work(i->to);
}

int main()
{
    fo1(i,N-1)for(int j=i;j<N;j+=i)v[j].push_back(i);
    fo(i,2,N-1)
    {
        if(!vis[i])pr[pm++]=i,phi[i]=i-1;
        for(int j=0;i*pr[j]<N;j++)
        {
            vis[i*pr[j]]=1;
            if(i%pr[j]==0)
            {
                phi[i*pr[j]]=phi[i]*pr[j];
                break;
            }
            phi[i*pr[j]]=phi[i]*(pr[j]-1);
        }
    }
    phi[1]=1;
    inv[1]=1;
    fo(i,2,N-1)inv[i]=(ll)(P-P/i)*inv[P%i]%P;
    fo1(i,N-1)
    {
        f[i]=(ll)i*inv[phi[i]]%P;
        foe(j,v[i])if(i^*j)(f[i]+=P-f[*j])%=P;
    }
    scanf("%d",&n);
    fo1(i,n)scanf("%d",w+i);
    fo0(i,n-1)
    {
        int x,y;
        scanf("%d%d",&x,&y);
        add(x,y);
        add(y,x);
    }
    mset(vis,0);
    mset(g,0xff);
    mset(h,0xff);
    work(1);
    ans=(ll)ans*inv[n]%P*inv[n-1]%P*2%P;
    printf("%d",ans);
}

日期： 2017-05-25

标签： Codeforces 数论 点分治

这是一篇旧文，原始文章及评论可在 https://oldblog.mcfx.us/archives/236/ 查看。