n<=10000000的图，满足：如果(i,j)>1就连一条边权1的无相变，问所有d(u,v) (u<=v)--u到v的最短路之和。
首先1和>n/2的质数都是孤立的点。然后两个数x,y如果(x,y)>1最短路就1，如果(x,y)=1且x,y都不是1或>n/2的质数一定能走，具体这么走：$P_x$--x的最小质因子，那就$x->p_x*p_y->y$，那这样都走不了，还有：$x->p_x*2->p_y*2->y$这种一定走得了，因为x或y如果是合数那$p_x$最大是根号的，再*2根本爆不了；如果是质数那由于<=n/2，所以自己*2一定不会爆，因此就统计1的路径数，2的路径数和3的路径数即可。
1的路径数：$sum_{1<=x<=n,1<=y<=n}(x,y)>1=sum_{x=1}^{n}x-1-varphi (x)$。
3的路径数用总的减掉1和2的。
2的路径数，也就是满足$(x,y)=1$且$p_x*p_y<=n$且$x>1,y>1$且x,y都不是大于n/2的质数的：
（1）x,y都是合数：那直接枚举合数，然后$sum_{y是合数}^{n} varphi (y)- (<=y的质数) + (x的质因子数)-1$，注意到这一条说的质数、质因子都是包括>n/2的。
（2）x质y合：那也枚举合数，$sum_{y是合数}^{n} s_y-(y的质因子数)$，其中$s_y$表示比$x*p_y<=n$的质数x的数量，注意到这一条说的质数、质因子都是不包括>n/2的。
（3）x质y质，那枚举质数，$sum_{y是质数}^{n} x*y<=n$，即$x<=n/y$，注意到这里枚举的质数是<=n/2的，而且这里统计的x也是<=n/2的。
OK！
1 #include<string.h> 2 #include<stdlib.h> 3 #include<stdio.h> 4 //#include<assert.h> 5 #include<algorithm> 6 //#include<iostream> 7 using namespace std; 8 9 int n; 10 #define maxn 10000011 11 int prime[maxn/10],lp=0,phi[maxn],small[maxn],sum[2][maxn],sonofbitch[2][maxn]; bool notprime[maxn]; 12 void pre(int n) 13 { 14 phi[1]=1; sum[0][1]=sum[1][1]=0; 15 for (int i=2;i<=n;i++) 16 { 17 sum[0][i]=sum[0][i-1]+(!notprime[i] && i*2<=n); 18 sum[1][i]=sum[1][i-1]+(!notprime[i]); 19 if (!notprime[i]) {prime[++lp]=i; phi[i]=i-1; sonofbitch[0][i]=(i*2<=n); 20 sonofbitch[1][i]=1; small[i]=i;} 21 for (int j=1;j<=lp && 1ll*i*prime[j]<=n;j++) 22 { 23 notprime[i*prime[j]]=1; small[i*prime[j]]=prime[j]; 24 if (i%prime[j]) 25 { 26 phi[i*prime[j]]=phi[i]*(prime[j]-1); 27 sonofbitch[0][i*prime[j]]=sonofbitch[0][i]+(prime[j]*2<=n); 28 sonofbitch[1][i*prime[j]]=sonofbitch[1][i]+1; 29 } 30 else 31 { 32 phi[i*prime[j]]=phi[i]*prime[j]; 33 sonofbitch[0][i*prime[j]]=sonofbitch[0][i]; 34 sonofbitch[1][i*prime[j]]=sonofbitch[1][i]; 35 break; 36 } 37 } 38 } 39 } 40 41 int main() 42 { 43 scanf("%d",&n); pre(n); 44 #define LL long long 45 LL tot1=0,tot2=0,tot3=0,m=n-(sum[1][n]-sum[0][n])-1,tot=m*1ll*(m-1)/2; 46 47 for (int i=2;i<=n;i++) tot1+=i-1-phi[i]; 48 49 for (int i=2;i<=n;i++) 50 if (notprime[i]) 51 tot2+=phi[i]-sum[1][i]+sonofbitch[1][i]-1+sum[0][n/small[i]]-sonofbitch[0][i]; 52 else if (i*2<=n) tot2+=sum[0][min(i-1,n/i)]; 53 54 tot3=tot-tot1-tot2; 55 56 printf("%lld ",tot1+tot2*2+tot3*3); 57 return 0; 58 }