题解 CF870F【Paths】

whiteqwq · 2021-05-10 10:24:59 · 题解

CF870F Paths解题报告：

更好的阅读体验

Codeforces Round 870考试总结

题意

## 分析好题。下面令$\mathbb{P}$为质数集合。首先不难发现$1$不可能与其他结点连边，因此直接不管$1$。然后对于点对$(x,y)$分情况讨论（设$minn_x$为$x$的最小质因子，$cnt_x$为$x$作为最小质因子在$[1,n]$的出现次数）： - $\gcd(x,y)>1$：$x$与$y$有一条长度为$1$的无向边，距离为$1$，这一类边的数量$tot1$显然等于$\frac{(n-1)(n-2)}{2}-\sum_{i=2}^n(\varphi(n)-1)

- - $$tot3=\sum_{i\in\mathbb{P}} \sum_{j\in \mathbb{P},j>i,j\leqslant\lfloor\frac{n}{2}\rfloor,ij>n}\sum_{x,y,minn_x=i,minn_y=j}[\gcd(x,y)=1]$$ 此时因为$i,j$分别是$x,y$的最小质因子，且$ij>n$，因此枚举的$x,y$的$\gcd$一定为一，那么化简一下： $$tot3=\sum_{i\in\mathbb{P}}cnt_i\sum_{j\in \mathbb{P},j>i,j\leqslant\lfloor\frac{n}{2}\rfloor,ij>n}cnt_j$$ 不难发现$j$的取值是一个区间$[\max\{\lfloor\frac{n}{i}\rfloor+1,i+1\},\lfloor\frac{n}{2}\rfloor]$，记$sum$为$cnt$的前缀和就可以快速计算了。
- - $$tot4=\sum_{i\in\mathbb{P}}cnt_i\sum_{j\in\mathbb{P},j>i,j>\lfloor\frac{n}{2}\rfloor,ij>n}cnt_j$$ 同样发现$j$的取值范围是区间$[\max\{\lfloor\frac{n}{2}\rfloor+1,i+1\},n]$。（这里没有在左区间的$\max$放入$\lfloor\frac{n}{i}\rfloor+1$的原因是它一定小于等于$\lfloor\frac{n}{2}\rfloor+1$）

上述数组可以用一次线性筛处理出来，加上统计时间复杂度仍为O(n)。

代码

#include<stdio.h>
#define int long long
const int maxn=10000005;
int n,pcnt,all,tot1,tot2,tot3,tot4;
int p[maxn],c[maxn],phi[maxn],cnt[maxn],minn[maxn],sum[maxn];
inline int max(int a,int b){
    return a>b? a:b;
}
inline int calc(int l,int r){
    return l>r? 0:sum[r]-sum[l-1];
}
signed main(){
    scanf("%lld",&n);
    c[1]=phi[1]=1;
    for(int i=2;i<=n;i++){
        if(c[i]==0)
            p[++pcnt]=i,minn[i]=i,phi[i]=i-1;
        for(int j=1;j<=pcnt;j++){
            if(i*p[j]>n)
                break;
            c[i*p[j]]=1,minn[i*p[j]]=p[j];
            if(i%p[j]==0){
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            phi[i*p[j]]=phi[i]*(p[j]-1);
        }
        cnt[minn[i]]++;
    }
    for(int i=1;i<=n;i++)
        sum[i]=sum[i-1]+cnt[i];
    all=tot1=(n-1)*(n-2)/2;
    for(int i=2;i<=n;i++)
        tot1-=(phi[i]-1);
    for(int i=1;i<=pcnt;i++){
        tot3+=cnt[p[i]]*calc(max(n/p[i]+1,p[i]+1),n/2);
        tot4+=cnt[p[i]]*calc(max(n/2+1,p[i]+1),n);
    }
    tot2=(n-1)*(n-2)/2-tot1-tot3-tot4;
    printf("%lld\n",tot1*1+tot2*2+tot3*3+tot4*0);
    return 0;
}