Description：

求 $\begin{align}\sum_{i=1}^nlcm(i,n)\end{align}$

Solution：

$\begin{align}\sum_{i=1}^n lcm(i,n)\end{align}$

$\begin{align}=\sum_{i=1}^n\frac {n\times i}{gcd(i,n)}\end{align}$

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

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

发现后面的求和号表示的就是与 $\frac n d$ 互质的数的和，于是

原式 $\begin{align}=n\times\sum_{d|n}(\frac {\frac n d\times \varphi(\frac n d)}{2}+\varepsilon(\frac n d))\end{align}$

$\begin{align}=n\times\sum_{d|n}\frac {d\times \varphi(d)}{2}+n\end{align}$

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int testcases;

int n;

#define MAXN 1000010

int prime[MAXN],tot = 0;

bool isprime[MAXN];

int phi[MAXN];

void init()

{

	for(register int i = 2;i < MAXN;++i)isprime[i] = true;

	phi[1] = 1;

	for(register int i = 2;i < MAXN;++i)

	{

		if(isprime[i])

		{

			prime[++tot] = i;

			phi[i] = i - 1;

		}

		for(register int j = 1;j <= tot && i * prime[j] < MAXN;++j)

		{

			isprime[i * prime[j]] = false;

			if(i % prime[j] == 0)

			{

				phi[i * prime[j]] = phi[i] * prime[j];

				break;

			}

			else

			{

				phi[i * prime[j]] = phi[i] * phi[prime[j]];

			}

		}

	}

	return;

}

inline int read()

{

	register int res = 0;

	register char c = getchar();

	while(!isdigit(c))c = getchar();

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res;

}

int main()

{

	init(); 

	scanf("%d",&testcases);

	for(register int i = 1;i <= testcases;++i)

	{

		n = read();

		register long long res = 0;

		int t = sqrt(n);

		for(register int k = 1;k <= t;++k)

		{

			if(n % k == 0)

			{

				res += (long long)(n / k) * phi[n / k] / 2;

				if(k * k != n)

				{

					res += (long long)(n / (n / k)) * phi[n / (n / k)] / 2;

				}

			}

		}

		res = (res + 1) * n;

		printf("%lld\n",res);

	}

	return 0;

}