【题目】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