我们枚举所有gcd \(k\)，求所有\(gcd=k\)的数对，记作\(f(k)\)，那么\(ans=\sum_{i=1}^{n}(f(i)-1)*i\)。为什么减1呢，观察题目，发现\(j=i+1\)，所以自己与自己的数对是不算的。

\(f(k)\)怎么求？

若\(a,b\)互质，则\(gcd(ak,bk)=k\)。

我们枚举\(a,b\)中较大的那个，记作\(i\)，那么另一个数就有\(φ(i)\)种可能，显然，\(1≤i≤n/k\)，所以\(f(k)=\sum_{i=1}^{n/k}φ(i)\)，用前缀和就行了。

时间复杂度\(O(n)\)

#include 
    
     const int MAXN = 100010;long long phi[MAXN], v[MAXN], prime[MAXN], cnt;int n;long long ans; int main(){    phi[1] = 1;    for(int i = 2; i <= 502; ++i){       if(!v[i]){         v[i] = i;         phi[i] = i - 1;         prime[++cnt] = i;       }       for(int j = 1; j <= cnt; ++j){          if(prime[j] > v[i] || prime[j] * i > 502) break;          v[i * prime[j]] = prime[j];          phi[i * prime[j]] = phi[i] * ((i % prime[j]) ? prime[j] - 1 : prime[j]);       }    }    for(int i = 2; i <= 502; ++i) phi[i] += phi[i - 1];    while(233){      scanf("%d", &n);      if(!n) return 0;      ans = 0;      for(int i = 1; i <= n; ++i) ans += (phi[n / i] - 1) * i;      printf("%lld\n", ans);    }    return 0;}