P1891 crazy LCM (Euler function)

Topic link ： Click here

The main idea of the topic ：
seek ${\sum }_{i=1}^{n}lcm(i,n)$

Topic analysis ：
The same way of thinking Yueyue gives Hua Hua a question
We know $lcm(i,n)=\frac{i\cdot n}{\gcd (i,n)}$
So the question is transformed into ${\sum }_{i=1}^n\frac{i\cdot n}{\gcd (i,n)}=n\cdot {\sum }_{i=1}^n\frac{i}{\gcd (i,n)}$
and
$$\sum _{i=1}^n\frac{i}{\gcd (i,n)}$$
$$=\sum _{d|n}\frac{1}{d}\sum _{i=1}^{n}i[\gcd (i,n)=d]$$
$$=\sum _{d|n}\frac{1}{d}\sum _{i=1}^{\lfloor \frac{n}{d}\rfloor }id[\gcd (i,n/d)=1]$$
$$=\sum _{d|n}\frac{n/d\cdot \phi (n/d)+[n/d=1]}{2}$$
$$=\sum _{d|n}\frac{d\cdot \phi (d)+[d=1]}{2}$$
Sift the Euler function in advance , Then, according to the above formula, the time complexity of harmonic series can be used to enumerate the enumeration factors to calculate the contribution
Then finally, for each group of input, use $n$ Multiply by the previously calculated value
The overall time complexity is $O(n\log n+t)$

See code for details ：

// Problem: P1891  insane  LCM
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1891
// Memory Limit: 125 MB
// Time Limit: 1000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define ll long long
#define inf 0x3f3f3f3f
#define Inf 0x3f3f3f3f3f3f3f3f
#define int ll
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
int read()
{
    
	int res = 0,flag = 1;
	char ch = getchar();
	while(ch<'0' || ch>'9')
	{
    
		if(ch == '-') flag = -1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9')
	{
    
		res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';
		ch = getchar();
	}
	return res*flag;
}
const int maxn = 1e6+5;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-8;
int n,cnt,pri[maxn],phi[maxn],ans[maxn];
bool vis[maxn];
void init(int n)
{
    
	vis[1] = phi[1] = 1;
	for(int i = 2;i <= n;i++)
	{
    
		if(!vis[i]) 
		{
    
			pri[++cnt] = i;
			phi[i] = i-1;
		}
		for(int j = 1;j<=cnt && i*pri[j]<=n;j++)
		{
    
			vis[i*pri[j]] = true;
			if(i%pri[j] == 0)
			{
    
				phi[i*pri[j]] = phi[i]*pri[j];
				break;
			}
			phi[i*pri[j]] = phi[i]*(pri[j]-1);
		}
	}
}
signed main() 
{
    
	n = maxn-1;
	init(n);
	for(int i = 1;i <= n;i++)
		for(int j = 1;j*i <= n;j++) ans[i*j] += phi[j]*j/2;
	// for(int i = 1;i <= n;i++) cout<<ans[i]+1<<endl;
	int t = read();
	while(t--)
	{
    
		n = read();
		printf("%lld\n",1LL*n*(ans[n]+1));
	}
	return 0;
}