题解 P1891 【疯狂 LCM】

\[ans=\sum_{i=1}^nlcm(i,n) \]

\[\begin{aligned} ans & =\sum_{i=1}^nlcm(i,n) \\ & =\sum_{i=1}^n\frac{i\cdot n}{gcd(i,n)} \\ & =n\times \sum_{i=1}^n\frac{i}{gcd(i,n)} \\ & =n\times\sum_{i=1}^ni\sum_{d=1}^i\frac{[gcd(i,n)=d]}{d} \\ & =n\times \sum_{d|n}\sum_{i=1}^{\left\lfloor\dfrac{n}{d}\right\rfloor}i\cdot[gcd(i,\frac{n}{d})=1] \end{aligned} \]

我们看后面的东西

---

\[g(n)=\sum_{i=1}^ni\cdot [gcd(i,n)=1] \]

我们知道更相减损术

\[gcd(a,b)=gcd(a,a-b) \]

所以

\[gcd(i,d)=1\Leftrightarrow gcd(d-i,d)=1 \]

所以

对于每一个i，都有另一个d-i与其对应，而且两个数的和是个定值！

所以

\[g(n)=\frac{\varphi(n)}{2}\times d \]

但是g(1)是个特例，所以要特别处理

g出来了之后我们再预处理答案，核心代码如下

for (int i = 1; i <= N; i++) {
		for (int j = i; j <= N; j += i) {
			S[j] += (g[i] * i + 1) >> 1;
		}
	}

这样就可以做到了。

#include
#define Starseven main
#define ll long long
namespace lyt {
	void read(int &x){
	char ch=getchar();int re=0,op=1;
	while(ch<'0'||ch>'9'){if(ch=='-') op=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){re=(re<<3)+(re<<1)+ch-'0';ch=getchar();}
	x = re * op;
	return ;
	}
	void read(long long &x){
	char ch=getchar();long long re=0,op=1;
	while(ch<'0'||ch>'9'){if(ch=='-') op=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){re=(re<<3ll)+(re<<1ll)+ch-'0';ch=getchar();}
	x = re * op;
	return ;
	}
	void write(int x){
		if(x<0){putchar('-');x=-x;}
		if(x>9) write(x/10);
		putchar(x%10+'0');
		return ;
	}//记得自己加空格和换行 
	void write(long long x){
		if(x<0){putchar('-');x=-x;}
		if(x>9) write(x/10);
		putchar(x%10+'0');
		return ;
	}//记得自己加空格和换行
	int max(int x,int y){return x> 1;//我这里没有特判1，而是用了一点小技巧
		}
	}
	while(t--) {
		int n;
		read(n);
		write(S[n] * n * 1ll);
		puts("");
	}
	return 0;	
}