【CodeForces】870 F. Paths

【题目】F. Paths

【题意】给定数字n，图上有编号为1~n的点，两点当且仅当gcd(u,v)≠1时有连边，定义d(u,v)为两点间最短距离（若不连通则为0），求Σd(u,v),1<=u<v<=n，n<=10^7。

【算法】数论

【题解】对于1<=x<=n，当x=1或x是大于n/2的素数时，x是孤立节点。

令p[x]表示x的最小素因子，考虑任意一对点的连边情况：

1.d=0：当至少一个点是孤立节点时，d(u,v)=0，否则都能通过下面的情况到达。

2.d=1：当gcd(u,v)≠1时，对数为one=Σx-1-φ(x),1<=x<=n。

3.d=2：p[u]*p[v]<=n时，可以通过u - p[u]*p[v] - v这条路径到达。（思路：两边最小素因子的乘积是最小中转点）

4.d=3：通过 u - 2*p[u] - 2*p[v] - v 到达。（思路：用最小的素因子2沟通）

通过情况1，容易计算出除了孤立节点外的点对总数sum。

情况2也容易计算（记为one），那么只须计算出情况3，情况4也可以用sum减去2和3得到。

如何计算满足p[u]*p[v]<=n&&gcd(u,v)=1的点对数？先计算满足p[u]*p[v]<=n（1<=u,v<=n）的点对数，然后减去u=v的情况，除以2后再减去one（u,v互素）即可得到。

复杂度O(n)。

#include<cstdio>

#include<cstring>

#include<algorithm>

#define ll long long

using namespace std;

const int maxn=;

int prime[maxn],p[maxn],n,tot,phi[maxn],num[maxn],can;

ll one=,two=,three=,s[maxn];

int main(){

    scanf("%d",&n);

    phi[]=;

    for(int i=;i<=n;i++){

        if(!p[i]){p[i]=prime[++tot]=i;phi[i]=i-;}

        for(int j=;j<=tot&&i*prime[j]<=n;j++){

            p[i*prime[j]]=prime[j];

            if(i%prime[j]==){phi[i*prime[j]]=phi[i]*prime[j];break;}

            phi[i*prime[j]]=phi[i]*(prime[j]-);

        }

    }

    for(int i=;i<=n;i++)one+=i--phi[i];

    for(int i=;i<=n;i++)num[p[i]]++;

    for(int i=;i<=n;i++)s[i]=s[i-]+num[i];

    for(int i=;i<=n;i++)two+=1ll*num[i]*s[n/i];

    for(int i=;i<=n;i++)if(1ll*p[i]*p[i]<=n)two--;

    two=two/-one;

    three=;can=n-;

    for(int i=;i<=tot;i++)if(prime[i]*>n)can--;

    three=1ll*can*(can-)/-two-one;

    printf("%lld",one*+two*+three*);

    return ;

}//learn from 1234567891

巴特西

【CodeForces】870 F. Paths

最新文章

热门文章