比较神奇的数学题。
重要的结论是<n且与n素质的数的和是phi(n)*n/2。
所以就枚举一下gcd就好了。
#include <cstdio>
#include <cctype>
#include <memory.h>
#include <algorithm>
using namespace std;
typedef long long qw;
#ifdef WIN32
#define lld "%I64d"
#else
#define lld "%lld"
#endif
#define _l (qw)
#define readInt(_s_) {\
int _d_;\
_s_ = 0;\
while (!isdigit(_d_ = getchar()));\
while ((_s_ = _s_ * 10 + _d_ - 48), isdigit(_d_ = getchar()));\
}
const int maxn = 1000009;
qw ans[maxn];
int tp, pn[maxn], phi[maxn];
bool pr[maxn];
void pre() {
memset(pr, 0, sizeof(pr));
tp = 0;
phi[1] = 1;
for (int i = 2; i < maxn; ++ i) {
if (!pr[i]) {
pn[tp ++] = i;
phi[i] = i - 1;
}
for (int j = 0; j < tp && i * pn[j] < maxn; ++ j) {
pr[i * pn[j]] = 1;
if (i % pn[j])
phi[i * pn[j]] = phi[i] * phi[pn[j]];
else {
phi[i * pn[j]] = phi[i] * pn[j];
break;
}
}
}
memset(ans, 0, sizeof(ans));
for (int i = 1; i < maxn; ++ i) {
for (int j = 2; j * i < maxn; ++ j)
ans[i * j] += _l i * j * j * phi[j] / 2;
}
for (int i = 1; i < maxn; ++ i)
ans[i] += i;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("in.txt", "r", stdin);
#endif
pre();
int t;
readInt(t);
while (t --) {
int x;
readInt(x);
printf(lld "\n", ans[x]);
}
}