<div class="post_brief"><p>
推了半天，发现还是得sqrt，过不到啊。</p>

 

然后发现与经典的问题相比，就是n=n。然后这不是做过的那个LCM sum的前缀和就完了嘛。傻了。

 

然后第一次MLE是因为明明压了8位，还是开了30长的数组。第二次WA是因为高精输出的时候%08d写成了%8d。是不是明天又要逗极而死了。

 

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;


typedef long long dint;


#define _l (long long int)


const int maxlen = 7;
const dint base = 1e8;
struct BigInt {
dint dig[maxlen], len;
BigInt() {
len = 0;
}
void set(dint x) {
dig[0] = x;
len = 1;
while (dig[len - 1] >= base) {
dig[len] = dig[len - 1] / base;
dig[len - 1] %= base;
++ len;
}
}
void copy(const BigInt& x) {
len = x. len;
for (int i = 0; i < len; ++ i)
dig[i] = x. dig[i];
}
void inc(dint x) {
if (!len) {
dig[0] = x;
len = 1;
}
else
dig[0] += x;
for (int i = 0; i < len - 1 && dig[i] >= base; ++ i) {
dig[i + 1] += dig[i] / base;
dig[i] %= base;
}
while (dig[len - 1] >= base) {
dig[len] = dig[len - 1] / base;
dig[len - 1] %= base;
++ len;
}
}
void print() {
printf("%d", (int)dig[len - 1]);
for (int i = len - 2; i >= 0; – i)
printf("%08d", (int)dig[i]);
putchar(10);
}
};


const int maxn = 1000009;


int tp, pn[maxn], phi[maxn];
dint tot[maxn];
BigInt ans[maxn];
bool pr[maxn];


void pre(int n) {
memset(pr, 0, sizeof(pr));
tp = 0;
phi[1] = 1;
for (int i = 2; i <= n; ++ i) {
if (!pr[i]) {
pn[tp ++] = i;
phi[i] = i - 1;
}
for (int j = 0, t; j < tp && (t = i * pn[j]) <= n; ++ j) {
pr[t] = 1;
if (i % pn[j])
phi[t] = phi[i] * phi[pn[j]];
else {
phi[t] = phi[i] * pn[j];
break;
}
}
}
for (int i = 1; i <= n; ++ i) {
dint d = (i == 1) ? 1 : (_l i * phi[i] >> 1);
for (int j = 1, t; (t = j * i) <= n; ++ j)
tot[t] += d;
}
ans[1]. set(1);
for (int i = 2; i <= n; ++ i) {
tot[i] = tot[i] * i;
ans[i]. copy(ans[i - 1]);
ans[i]. inc(tot[i] * 2 - i);
}
}


int main() {
#ifndef ONLINE_JUDGE
freopen(“in.txt”, “r”, stdin);
#endif


int t;
scanf("%d", &amp;t);
pre(1e6);
while (t --) {
	int n;
	scanf("%d", &amp;n);
	ans[n]. print();
}



}