Cod sursa(job #597219)
#include <fstream>
using namespace std;
int X, N;
int prims[1002];
bool isprim[100002];
int fact[10];
int Log[1 << 7], nrB[1 << 7];
void ciur()
{
prims[++prims[0]] = 2;
for (int i = 3; i * i<= 100000; i += 2)
if (!isprim[i])
{
prims[++prims[0]] = i;
for (long long j = i * i; j <= 100000; j += 2 * i)
isprim[j] = true;
}
}
int main()
{
ifstream fin("sum.in");
ofstream fout("sum.out");
nrB[1] = 1;
for (int i = 2; i < (1 << 7); ++i)
{
Log[i] = Log[i >> 1] + 1;
nrB[i] = nrB[i & (i - 1)] + 1;
}
ciur();
fin >> N;
while (N--)
{
long long sumnow = 0;
fin >> X;
fact[0] = 0;
int aux = X;
for (int i = 1; prims[i] * prims[i] <= X && i <= prims[0]; ++i)
if (aux % prims[i] == 0)
{
fact[++fact[0]] = prims[i];
while (aux % prims[i] == 0)
aux /= prims[i];
}
if (aux != 1) fact[++fact[0]] = aux;
for (int i = 1; i < (1 << (fact[0])); ++i)
{
int now = 1;
int clone = i;
while (clone)
{
now *= fact[Log[clone & -clone] + 1];
clone &= clone - 1;
}
int times = (2 * X) / now;
long long snow = 0;
snow += 1LL * times * (times + 1);
snow *= 1LL * now;
if (nrB[i] & 1) sumnow += snow;
else sumnow -= snow;
}
sumnow /= 2;
fout << 1LL * 2 * X * (2 * X + 1) / 2 - sumnow << '\n';
}
fin.close();
fout.close();
}