「Codeforces 870F」Paths

给定数字 $n$ ，建立一个无向图。对于所有 $1$ 到 $n$ 之间的数字，当数字 $gcd(u,v)\neq 1$ 时将 $u$、$v$ 连一条边，边权为 $1$ 。$d(u,v)$ 表示 $u$ 到 $v$ 的最短路，求所有 $d(u,v)$ 的和，其中 $1\leq u < v \leq n$。

Constraints

$1 \leq n \leq 10^7 $

Solution

对于 $1$ 以及所有大于 $\frac{n}{2}$ 的质数，与其他数字均不联通，直接剔除。

对于剩下的数字：

$1.$ 当 $gcd(u,v) \neq 1$ 时，$d(u,v)=1$ 。即对于数字 $u$，小于 $u$ 且 $d(u,v)=1$ 的数字个数为 $x-1-\varphi (x)$ 。

$2.$ 令 $p[u]$ 表示数字 $u$ 的最小质因子，则当 $p[u]\cdot p[v]\leq n$ 时，$d(u,v)=2$ 。维护数组 $num$ 、$sum$ ， $num[i]$ 代表最小质因子为 $i$ 的数字个数， $sum$ 数组为 $num$ 数组的前缀和。统计 $\sum num[i]\cdot sum[n/i]$ 可以覆盖所有 $p[u]\cdot p[v] \leq n$ 的情况，其中减去自身与自身被统计的情况，剩下的所有数对都被统计了两次，其中包含 $gcd(u,v)\neq 1$ 的情况，需进行相应处理，详见代码。

$3.$ 剩下的数对最短路一定为 $3$ ，因为 $u$ → $2\cdot p[u]$ → $2\cdot p[v]$ → $v$ 这条路一定存在。可通过数对总数减去 $d(u,v)=1$ 与 $d(u,v)=2$ 的情况得到。

Code

#include<cstdio>
#include<cstring>
#include<algorithm>
#define LL long long
using namespace std;
const int N=1e7+5;
int n,m,tot,now,pri[N],p[N],phi[N],num[N],sum[N]; 
LL one,two,three;
int main()
{
    scanf("%d",&n);
    phi[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!p[i]){p[i]=pri[++tot]=i;phi[i]=i-1;}
        for(int j=1;j<=tot;j++)
        {
            if(i*pri[j]>n)break;
            p[i*pri[j]]=pri[j];
            if(i%pri[j]==0){phi[i*pri[j]]=phi[i]*pri[j];break;}
            else phi[i*pri[j]]=phi[i]*(pri[j]-1);
        }
    } 
    for(int i=2;i<=n;i++)one+=i-1-phi[i];
    for(int i=2;i<=n;i++)num[p[i]]++;
    for(int i=2;i<=n;i++)sum[i]=sum[i-1]+num[i];
    for(int i=2;i<=n;i++)two+=1ll*num[i]*sum[n/i];
    for(int i=2;i<=n;i++)if(1ll*p[i]*p[i]<=n)two--;
    two=two/2-one;m=n-1;
    for(int i=tot;i>=1;i--)
        if(pri[i]*2>n)m--;
        else break;
    three=1ll*m*(m-1)/2-one-two;
    printf("%lld\n",one+two*2+three*3);
    return 0;
}