题目要求求：
[sum_{i=1}^nlcm(i,n)
]
先转化成gcd处理：
[nsum_{i=1}^nfrac{i}{gcd(i,j)}
]
之后老套路 枚举gcd，并且先把d除进去之后用(i)代替(frac{i}{d})
[n sum_{d|n}isum_{i=1}^{frac{n}{d}}[gcd(i,frac{n}{d})=1]
]
这时候发现 后面那一项其实是要求求在(frac{n}{d})以内所有与其互质的数的和。因为当(gcd(d,i) = 1)时，(gcd(d-i,i) = 1),所以这样的数一定是成对出现，有(frac{1}{2}varphi(n))对，所以就可以计算这个值。注意当n=1的时候，这个值是1.所以要在后面加上1.
我们现在要求的就是
[nsum_{d|n}frac{frac{n}{d}varphi(frac{n}{d})}{2} + n
]
这玩意咋求呢……？我们首先线性把欧拉函数筛出来，之后虽然他有枚举因子的循环，但实际上我们也这么操作，他每次做的操作次数之和其实是一个调和级数（很像埃氏筛法），是(O(nlogn))的。所以直接这样先预处理出来，之后询问的时候(O(1))出结果即可。
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<iostream>
#include<cmath>
#include<set>
#include<vector>
#include<map>
#include<queue>
#define rep(i,a,n) for(int i = a;i <= n;i++)
#define per(i,n,a) for(int i = n;i >= a;i--)
#define enter putchar('
')
#define fr friend inline
#define y1 poj
#define mp make_pair
#define pr pair<int,int>
#define fi first
#define sc second
#define pb push_back
#define I puts("bug")
using namespace std;
typedef long long ll;
const int M = 1000005;
const int INF = 1000000009;
const double eps = 1e-7;
const double pi = acos(-1);
const ll mod = 1e9+7;
ll read()
{
ll ans = 0,op = 1;char ch = getchar();
while(ch < '0' || ch > '9') {if(ch == '-') op = -1;ch = getchar();}
while(ch >= '0' && ch <= '9') ans = ans * 10 + ch - '0',ch = getchar();
return ans * op;
}
int T,n,p[M],phi[M],tot;
bool np[M];
ll ans[M];
void euler()
{
np[1] = 1,phi[1] = 1;
rep(i,2,M-2)
{
if(!np[i]) p[++tot] = i,phi[i] = i-1;
for(int j = 1;i * p[j] <= M-2;j++)
{
np[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);
}
}
rep(i,1,M-2)
for(int j = 1;j * i <= M-2;j++) ans[i * j] += (ll)i * phi[i] / 2;
rep(i,1,M-2) ans[i] = (ll)ans[i] * i + i;
}
int main()
{
euler();
T = read();
while(T--) n = read(),printf("%lld
",ans[n]);
return 0;
}