考察

$$\sum_{i=1}^{n} lcm(i,n)=\sum_{i=1}^{n} in/gcd(i,n)$$$$=n\sum_{i=1}^{n} i/gcd(i,n)$$

那我们可以计算对于每个$d$作为$gcd(i,n)$时，它对答案的贡献，就有

$$=n\sum_{d|n}\sum_{i=1}^{n} \frac{i}{d}[gcd(i,n)==d]$$

考虑到如果$gcd(i,n)==d$，必然有$i$为$d$的倍数，因此不妨将i的意义转化为原来的$i/d$,也即

$$=n\sum_{d|n}\sum_{i=1}^{n/d} \frac{i}{d}[gcd(id,n)==d]$$$$=n\sum_{d|n}\sum_{i=1}^{n/d} i[gcd(i,n/d)==1]$$ $$=n\sum_{d|n}\sum_{i=1}^{d} i[gcd(i,d)==1]$$

注意到$\sum_{i=1}^{d} i[gcd(i,d)==1]$表示$[1,d]$中与$d$互质的数的和，它等于$\frac{\varphi(d)d}{2}$(当$d=1$时为$1$)。证明如下：

当$d>1$时，$\varphi(d)$总是偶数，这是因为与$d$互质的数总是成对出现。具体来说，假如$i$与$d$互质，$d-i$与$d$肯定也互质，它们的和是$d$，并且有$\varphi(d)/2$对。

于是上式化简为

$$=n\sum_{d|n}\frac{\varphi(d)d}{2}$$

设

$$f(d)=\sum_{d|n}\frac{\varphi(d)d}{2}$$

那么对于每个$1\le d\le n$,我们只要把$\frac{\varphi(d)d}{2}$加到$f(dj)$中去,询问时再把最外面那个$n$乘进去。复杂度是$O(nlogn+T)$

#include <cstdio>
const int N=1000000;
int tot,p[N+5],phi[N+5];
long long ans[N+5];
bool flg[N+5];

void solve() {
    phi[1]=1;
    for(int i=2;i<=N;++i) {
        if(!flg[i]) p[++tot]=i,phi[i]=i-1;
        for(int j=1;j<=tot&&i*p[j]<=N;++j) {
            flg[i*p[j]]=1;
            if(i%p[j]==0) {
                phi[i*p[j]]=phi[i]*p[j];
                break;
            }
            phi[i*p[j]]=phi[i]*(p[j]-1);
        }
    }
    for(int i=1;i<=N;++i) {
        for(int j=1;i*j<=N;++j) {
            ans[i*j]+=1LL*j*phi[j]/2;
        }
    }
    for(int i=1;i<=N;++i) ans[i]=1LL*i*ans[i]+i;
}
int main() {
    int T,n;
    solve();
    for(scanf("%d",&T);T;--T) {
        scanf("%d",&n);
        printf("%lld\n",ans[n]);
    }
    return 0;
}