CF870F Paths解题报告

解题报告

CF870F Paths解题报告：

更好的阅读体验

Codeforces Round 870考试总结

题意

$n$个顶点的图，对于点对$i,j$，如果$\gcd(i,j)>1$那么$i,j$之间有一条长度为$1$的无向边，求图上点对两两之间距离之和。（如果无法到达则距离为$0$）

分析

好题。

下面令$\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)$
• $\gcd(x,y)=1$，继续分情况讨论：
• • $minn_x\times minn_y\leqslant n$，很显然$x$可以到达$minn_x\times minn_y$，然后再到达$y$，距离为$2$，这一类边我不知道为什么总会统计错，最后只能用总点对减去无法到达与其他距离的点对来计算/kk。
• • $minn_x\times minn_y>n$，继续分情况讨论（不妨设$minn_x\leqslant minn_y$）：
• • • $minn_y\leqslant \lfloor\frac{n}{2}\rfloor$，此时有一条这样的路径：$x\leftrightarrow 2minn_x\leftrightarrow2minn_y\leftrightarrow y$（很显然用$3$以及更大的数作为倍数一定不优于$2$），距离为$3$，这一类边的数量为：
      $$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$的前缀和就可以快速计算了。
• • • $minn_y>\lfloor\frac{n}{2}\rfloor$，此时发现无论如何都没有办法从$x$到达$y$，距离为$0$，这一类边的数量为：
      $$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;
}