「bzoj2226」「Spoj5971」LCMSum - 莫比乌斯反演

题目大意

    计算$\sum_{i=1}^nlcm(i,n)$。

---

题目分析

$$\begin{aligned} \sum_{i=1}^nlcm(i,n)&=\sum_{i=1}^n\frac{i\cdot n}{\gcd(i,n)} \\ &=\sum_{d\mid n}\sum_{i=1}^n\frac{i\cdot n}{d}[\gcd(i,n)=d] \\ &=n\sum_{d\mid n}\sum_{i=1}^n\frac{i}{d}[\gcd(i,n)=d] \\ &=n\sum_{d\mid n}\sum_{i=1}^{\frac nd}i[\gcd(i,\frac nd)=1] \\ &=n\sum_{d\mid n}\sum_{i=1}^{d}i[\gcd(i,d)=1]\quad\text{因为枚举}d\text{，因此}\frac nd\text{与}d\text{等价} \end{aligned}$$

令$f[d]=\sum\limits_{i=1}^{d}i[\gcd(i,d)=1]$，故原式为：$n\sum\limits_{d\mid n}f[d]$。
考虑如何求$f[d]$，我们发现$f[d]$有具体意义：比$d$小且与$d$互质的数之和，在本处我们讲过$f[d]=\frac{d\varphi(d)}2$。
故答案为：

$$n\sum_{d\mid n}\frac{d\varphi(d)}2$$

一种解法是线性筛$\varphi$，对于询问$O(\sqrt n)$回答，总时间复杂度$O(T\sqrt n)$，无法通过（似乎有人卡常数过了）。
我们可以用$O(n\log n)$的时间进行预处理将答案普通筛一遍，回答询问就是$O(1)$的了。

另：本题似乎有其他反演的方式，最后可以直接线性筛得出答案。

---

代码

#include<algorithm>
#include<iostream>
#include<iomanip>
#include<cstring>
#include<cstdlib>
#include<climits>
#include<vector>
#include<cstdio>
#include<cmath>
#include<queue>
using namespace std;

typedef long long LL;

inline const int Get_Int() {
	int num=0,bj=1;
	char x=getchar();
	while(x<'0'||x>'9') {
		if(x=='-')bj=-1;
		x=getchar();
	}
	while(x>='0'&&x<='9') {
		num=num*10+x-'0';
		x=getchar();
	}
	return num*bj;
}		

const int maxn=1000005;

LL n,ans[maxn];
int cnt=0,Prime[maxn],Phi[maxn];
bool vst[maxn]; 

void Table(int n) {
	Phi[1]=1;
	for(int i=2; i<=n; i++) {
		if(!vst[i]) {
			Prime[++cnt]=i;
			Phi[i]=i-1;
		}
		for(int j=1; j<=cnt&&i*Prime[j]<=n; j++) {
			vst[i*Prime[j]]=1;
			if(i%Prime[j]==0) {
				Phi[i*Prime[j]]=Phi[i]*Prime[j];
				break;
			}
			Phi[i*Prime[j]]=Phi[i]*Phi[Prime[j]];
		}
	}
}

int main() {
	Table(1000000);
	for(int i=2; i<=1000000; i++)
		for(int j=i; j<=1000000; j+=i)
			ans[j]+=(LL)i*Phi[i]/2;
	int t=Get_Int();
	while(t--) {
		n=Get_Int();
		printf("%lld\n",(ans[n]+1)*n);
	}
	return 0;
}