loj6375题解

好久没怎么做题了，做道水题练练手.

$$\begin{aligned}&\sum\mathrm{lcm}(i,n)\\\\=&n\sum\frac{i}{\gcd(i,n)}\\\\=&n\sum _{d|n}\frac{1}{d}\sum _{i=1}^{n/d}di[\gcd(i,n/d)=1]\end{aligned}$$

记$f(n)=\sum _{i=1}^ni[\gcd(i,n)=1]$，那么当$n>1$的时候均有$f(n)=\frac{n\varphi(n)}{2}$，而答案即为$n\sum _{d|n}f(\frac{n}{d})$.

预处理欧拉函数就可以了.

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#define ele long long
using namespace std;
#define maxn 1000010
ele n,pcnt,plst[maxn],phi[maxn];
bool flag[maxn];
inline ele f(ele n){
	return n==1?1:n*phi[n]/2;
}
int main(){
	freopen("lcm.in","r",stdin); freopen("lcm.out","w",stdout);
	pcnt=0; phi[1]=1;
	memset(flag,0,sizeof(flag));
	for (int i=2; i<maxn; ++i){
		if (!flag[i]) plst[pcnt++]=i,phi[i]=i-1;
		for (int j=0; j<pcnt && i*plst[j]<maxn; ++j){
			flag[i*plst[j]]=true;
			if (i%plst[j]) phi[i*plst[j]]=phi[i]*phi[plst[j]];
			else{
				phi[i*plst[j]]=phi[i]*plst[j];
				break;
			}
		}
	}
	ele T;
	scanf("%lld",&T);
	while (T--){
		scanf("%lld",&n);
		ele ans=0;
		for (ele d=1; d*d<=n; ++d)
			if (n%d==0){
				ans+=f(n/d);
				if (d*d!=n) ans+=f(d);
			}
		printf("%lld\n",ans*n);
	}
	return 0;
}