原题：P1891 疯狂 LCM

推式子：

$$\begin{align} &\sum\limits_{i=1}^nlcm(i,n)\notag\\ &=\sum\limits_{d|n}d^{-1}\sum\limits_{i=1}^nin[\gcd(i,n)=d]\notag\\ &=n\sum\limits_{d|n}d^{-1}\sum\limits_{i=1}^{\frac{n}{d}}id[\gcd(i,\frac{n}{d})=1]\notag\\ &=n\sum\limits_{d|n}\sum\limits_{i=1}^{\frac{n}{d}}i[\gcd(i,\frac{n}{d})=1]\notag\\ \end{align} $$

我们发现，与$x$互质的数总是成对出现，且每一对和为$x$。因此，

$$\begin{align} &\sum\limits_{i=1}^{\frac{n}{d}}i[\gcd(i,\frac{n}{d})=1]\notag =&\frac{\varphi(\frac{n}{d})\frac{n}{d}}{2}\notag\\ \end{align} $$

我们记他为$f$。这个可以$O(1)$求。 注意，当$i=1$时$f(i)$的值比较特殊，需要特判。

最后我们可以$O(nlnn)$求出所有n的值。

你当然可以用$DiRiChLeT$前缀和来达到$O(n\:ln\:ln\:n)$，但是在本题中并不需要。

#include<bits/stdc++.h>
#define int long long
using namespace std;
int n,T;
const int N=1e6*1.01;
bitset<N>pvis;
int pri[N],ptot,phi[N];
int F(int x){
	if(x==1) return 1;
	return x*phi[x]/2;
}int ans[N];
signed main() {
	for(int i=2;i<=N;i++){
		if(pvis[i]==0){
			pri[++ptot]=i;
			phi[i]=i-1;
		}for(int j=1;pri[j]*i<=N&&j<=ptot;j++){
			pvis[i*pri[j]]=1;
			if(i%pri[j]==0){
				phi[i*pri[j]]=phi[i]*pri[j];
				break;
			}phi[i*pri[j]]=phi[i]*(pri[j]-1);
		}
	}for(int i=1;i<=N;i++){
		for(int j=i;j<=N;j+=i){
			ans[j]=ans[j]+F(j/i);
		}ans[i]*=i;
	}
	ios::sync_with_stdio(0);
	cin.tie(0);
	cin>>T;
	while(T--){
		cin>>n;
		cout<<ans[n]<<"\n";
	}
	return 0;
}