思路

将题意转化为$\sum_{i = 1}^{n} \sum_{j = 1}^{i - 1}gcd(i, j)$，考虑每个最大公因数的值$k$对答案的影响。假设

$gcd(A,B) = k$

那么肯定可以表示成

$gcd(ak,bk) = k$

$gcd(a, b) = 1$

假设$a>b$那么$b$有$\varphi (a)$种选法且$ak \leq n$等价于$a \leq \left \lfloor \frac{n}{k} \right \rfloor$，因此对于一种$k$，它对答案的贡献为

$\sum_{a = 2}^{\left \lfloor \frac{n}{k} \right \rfloor} k*\varphi (a)$

$k \sum_{a = 1}^{\left \lfloor \frac{n}{k} \right \rfloor} \varphi (a) - k$

$k (\sum_{a = 1}^{\left \lfloor \frac{n}{k} \right \rfloor} \varphi (a) - 1)$

所以

$ans = \sum_{k = 1}^{n} k (\sum_{a = 1}^{\left \lfloor \frac{n}{k} \right \rfloor} \varphi (a) - 1)$

维护欧拉函数前缀和之后整除分块，时间复杂度$O(n+\sqrt{n})$

代码

#include 
     
      #include 
      
       #include 
       
        #include 
        
         #define DBG(x) cerr << #x << " = " << x << endlusing namespace std;typedef long long LL;const int N = 1e7 + 5;int n;int tag[N], pri[N], cnt;LL phi[N];LL pre[N];void getPrime() {    phi[1] = 1;    for(int i = 2; i < N; i++) {        if(!tag[i]) {            pri[cnt++] = i;            phi[i] = i - 1;        }        for(int j = 0; j < cnt && i * pri[j] < N; j++) {            tag[i * pri[j]] = 1;            if(i % pri[j] == 0) {                phi[i * pri[j]] = phi[i] * pri[j];                break;            }            phi[i * pri[j]] = phi[i] * (pri[j] - 1);        }    }    for(int i = 1; i < N; i++) pre[i] = pre[i - 1] + phi[i];}int main() {    getPrime();    while(~scanf("%d", &n) && n != 0) {        LL ans = 0;        for(LL l = 1, r; l <= n; l = r + 1) {            r = 1LL * n / (1LL * n / l);            LL tmp1 = ((r + l) * (r - l + 1)) / 2LL;            LL tmp2 = pre[n / l] - 1LL;            ans += tmp1 * tmp2;        }        printf("%lld\n", ans);    }    return 0;}/*101002000000*/