SUM_GCD

- $f[k]$表示$gcd(i,j)==k$的个数，那么答案就是$ \sum_{k=1}^nk*f[k]$; - 设一个辅助函数$g[k]$表示$k|gcd(i,j)$的个数，那么 $f[k]=g[k]-(f[2*k]+f[3*k]+......+f[n/k*k]);$ - 如果想要$k|gcd(i,j)$,只要让i和j都是k的倍数就行了，那么i和j的取值都有$n/k$种，所以$g[k]=(n/k)*(n/k)$; - 复杂度是调和级数，完全可以通过这道题。