Codeforces 809E：Surprise me! (모 비 우 스 재연 + 허수 수)

제목 전송 문:http://codeforces.com/contest/809/problem/E
제목 분석: 극점 까지 의 틀 에 박 힌 문제.
공식 적 으로 유도 하여 직접 보다.https://blog.sengxian.com/solutions/cf-809e, QAQ 하기 귀찮아 요.
마지막 출시:
ans=∑T=1n∑d|Tdμ(Td)ϕ(d)∑d|ai∑d|ajϕ(ai)ϕ(aj)dis(i,j) a n s = ∑ T = 1 n ∑ d | T d μ ( T d ) ϕ ( d ) ∑ d | a i ∑ d | a j ϕ ( a i ) ϕ ( a j ) d i s ( i , j )
두 번 째 ∑ 뒤의 물건 을 G (T) G (T) 로 기록 하면 이것 은 O (nln (n) O (n ln ⁡ (n)) 로 미리 처리 할 수 있다.그리고 모든 만족 d | ai d | a i 의 점 i 에 대해 허 수 를 만 들 고 허 수 중의 임의의 한 변 을 매 거 하 며 이 변 의 길이 로 좌우 양쪽 을 곱 합 니 다.ϕ ϕ 공헌 할 가치 가 있 는 답안.a 는 1 ~ n 의 한 배열 이기 때문에 허수 의 총 크기 는 nln (n) n ln ⁡ (n) 이다.ST 표 로 예비 처 리 를 하면 O (1) O (1) 가 LCA 를 구 할 수 있다.모든 조건 을 만족 시 키 는 점 i 를 시간 스탬프 에 따라 정렬 하면 시간 복잡 도 여러 log log.처음에는 모든 점 을 정렬 한 다음 순서대로 vector 에 삽입 할 수 있 습 니 다.매 거 인 수 를 해 야 하기 때문에 시간 은 ∑ ni = 1i √ ∑ i = 1n i 이 고 대략 6 ∗ 107 6 ∗ 10.7 이다.
처음에는 허수아비 의 변 권 이 1 (naive!) 인 줄 알 고 WA 가 한 번 했다.나중에 RE 가 되 었 습 니 다. 저 는 vector 의 문제 인 줄 알 았 습 니 다.
그래서 제 가 이 문 제 를 푸 는 것 은 바로 허 수 를 쓰 는 연습 을 하기 위해 서 입 니 다. 이것 은 아마 마지막 허 수 문제 일 것 입 니 다.
그리고 나 서 나 는 코드 에 있 는 빈 나무의 템 플 릿 을 뽑 았 다.

tail=1;
sak[1]=tree[1];
for (int i=2; i<=Node[d].size(); i++)
{
    int x=tree[i],last=0,p=Lca(sak[tail],x);
    while ( dep[ sak[tail] ]>dep[p] && tail ) last=sak[tail--];
    if (sak[tail]!=p) Fa[p]=sak[tail],sak[++tail]=tree[++cnt]=p;
    if (last) Fa[last]=p;
    Fa[x]=p;
    sak[++tail]=x; //!!!
}
int root=sak[1];
Fa[root]=0;

이 코드 는 자신 이 가상 나무 에 대한 이해 YY 에 따라 나 온 것 이기 때문에 매우 간단 하 다 (chou) 결 (lou). 순 전 히 자신 에 게 시간 이 있 을 때 보 여 주 는 것 이 고 뿌리 는 것 을 좋아 하지 않 는 다.
이 문 제 는 원래 1h 를 계획 한 것 이 었 는데 1h 때 코드 를 다 쳤 고 25min 이 지나 서 야 조정 되 었 으 며 코드 능력 은 강화 해 야 한다.
CODE：

#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;

const int maxn=200100;
const int maxl=20;
const long long M=1000000007;
typedef long long LL;

struct edge
{
    int obj;
    edge *Next;
} e[maxn<<1];
edge *head[maxn];
int cur=0;

vector <int> Node[maxn];

int Rank[maxn];
int dep[maxn];
int dfn[maxn];
int Time=0;

int Lg[maxn<<1];
int dfsx[maxn<<1];
int ST[maxn<<1][maxl];

int tree[maxn];
int cnt;
int sak[maxn];
int tail;

LL Size[maxn];
int Fa[maxn];

int phi[maxn];
int miu[maxn];

LL rev[maxn];
LL G[maxn];

bool vis[maxn];
int prime[maxn];
int num=0;

int a[maxn];
int n;
LL ans=0;

void Add(int x,int y)
{
    cur++;
    e[cur].obj=y;
    e[cur].Next=head[x];
    head[x]=e+cur;
}

void Linear_shaker()
{
    phi[1]=miu[1]=1;
    for (int i=2; i<=n; i++)
    {
        if (!vis[i]) phi[i]=i-1,miu[i]=-1,prime[++num]=i;
        for (int j=1; j<=num && i*prime[j]<=n; j++)
        {
            int k=i*prime[j];
            vis[k]=true;
            if (i%prime[j])
            {
                phi[k]=phi[i]*(prime[j]-1);
                miu[k]=-miu[i];
            }
            else
            {
                phi[k]=phi[i]*prime[j];
                miu[k]=0;
                break;
            }
        }
    }

    rev[1]=1;
    for (LL i=2; i<=n; i++)
    {
        LL x=M/i,y=M%i;
        rev[i]=x*rev[y]%M;
        rev[i]=M-rev[i];
    }

    for (int i=1; i<=n; i++) if (miu[i]==-1) miu[i]=M-1;
    for (int i=1; i<=n; i++)
        for (int j=1; i*j<=n; j++)
            G[i*j]=(G[i*j]+ (long long)i*miu[j]%M*rev[ phi[i] ]%M )%M;
}

void Dfs(int node,int fa)
{
    dfn[node]=++Time;
    dfsx[Time]=node;
    for (edge *p=head[node]; p; p=p->Next)
    {
        int son=p->obj;
        if (son==fa) continue;
        dep[son]=dep[node]+1;
        Dfs(son,node);
        dfsx[++Time]=node;
    }
}

bool Comp(int x,int y)
{
    return dfn[x]int Lca(int x,int y)
{
    x=dfn[x],y=dfn[y];
    if (x>y) swap(x,y);
    int lg=Lg[y-x];
    y=y-(1<1;
    x=ST[x][lg];
    y=ST[y][lg];
    if (dep[x]return x;
    return y;
}

void Calc(int node)
{
    for (edge *p=head[node]; p; p=p->Next)
    {
        int son=p->obj;
        Calc(son);
        Size[node]=(Size[node]+Size[son])%M;
    }
}

int main()
{
    freopen("c.in","r",stdin);
    freopen("c.out","w",stdout);

    scanf("%d",&n);
    for (int i=1; i<=n; i++) scanf("%d",&a[i]),head[i]=NULL;
    for (int i=1; iint x,y;
        scanf("%d%d",&x,&y);
        Add(x,y);
        Add(y,x);
    }

    Linear_shaker();

    dep[1]=1;
    Dfs(1,1);

    for (int i=1; i<=Time; i++) ST[i][0]=dfsx[i];
    for (int j=1; jfor (int i=1; i<=Time; i++)
        {
            int mid=min(i+(1<1)),Time);
            if (dep[ ST[i][j-1] ]1] ]) ST[i][j]=ST[i][j-1];
            else ST[i][j]=ST[mid][j-1];
        }
    Lg[1]=0;
    for (int i=2; i<=Time; i++) Lg[i]=Lg[i>>1]+1;

    for (int i=1; i<=n; i++) Rank[i]=i;
    sort(Rank+1,Rank+n+1,Comp);
    for (int i=1; i<=n; i++)
    {
        int node=Rank[i];
        int max_d=(int)floor( sqrt( (double)a[node] )+0.001 );
        for (int d=1; d<=max_d; d++)
            if (a[node]%d==0)
            {
                Node[d].push_back(node);
                if (d!=a[node]/d) Node[ a[node]/d ].push_back(node);
            }
    }

    for (int d=1; d<=n; d++)
    {
        cnt=0;
        for (int i=0; i1;
        sak[1]=tree[1];
        for (int i=2; i<=Node[d].size(); i++)
        {
            int x=tree[i],last=0,p=Lca(sak[tail],x);
            while ( dep[ sak[tail] ]>dep[p] && tail ) last=sak[tail--];
            if (sak[tail]!=p) Fa[p]=sak[tail],sak[++tail]=tree[++cnt]=p;
            if (last) Fa[last]=p;
            Fa[x]=p;
            sak[++tail]=x; //!!!
        }
        int root=sak[1];
        Fa[root]=0;

        cur=0;
        for (int i=1; i<=cnt; i++) head[ tree[i] ]=NULL;
        for (int i=1; i<=cnt; i++)
        {
            int x=tree[i];
            if (Fa[x]) Add(Fa[x],x);
            if (i<=Node[d].size()) Size[x]=phi[ a[x] ];
            else Size[x]=0;
        }

        Calc(root);
        LL tot=Size[root],temp=0;
        for (int i=1; i<=cnt; i++)
        {
            int x=tree[i];
            if (x==root) continue;
            temp=(temp+ Size[x]*(tot-Size[x]+M)%M*(dep[x]-dep[ Fa[x] ])%M )%M; //!!!
        }
        temp=temp*G[d]%M;
        ans=(ans+temp)%M;
    }

    ans=ans*rev[n]%M;
    ans=ans*rev[n-1]%M;
    ans=ans*2LL%M;
    printf("%I64d
",ans);

    return 0;
}