题意描述

link

求 \(\displaystyle\sum_{i=1}^{n}lcm(i,n)\) ， \(n\leq 10^6\)

solution

反演题。

首先有： \(\displaystyle\sum_{i=1}^{n}lcm(i,n) = \sum_{i=1}^{n} {i\times n\over gcd(i,n)}\)

然后提出一个 \(n\) 来可得：

\(\displaystyle n\sum_{i=1}^{n} i * {1\over gcd(i,n)}\)

然后考虑枚举一下 \(d\) 可得：

\(\displaystyle n\sum_{i=1}^{n}\sum_{d=1,d\mid n,d\mid i}^{n} {i\over d}[gcd(i,n) == d]\)

同除 \(d\) (把 \(i\) 换成 \(i\over d\)) ,同时交换一下求和顺序可得：

\(\displaystyle\sum_{d\mid n}\sum_{i=1}^{n\over d} i[gcd(i,{n\over d}) == 1]\)

后面你会发现他求的是 \({n\over d}\) 的范围内，与 \({n\over d}\) 互质的个数的和·，他就等于 \({n\over d}*\varphi({n\over d})\over 2\).

然后柿子就变为 \(\displaystyle\sum_{d\mid n} {n\over d} * \varphi({n\over d}) * {1\over 2}\) .

但当 \({n \over d} = 1\) 的时候，他柿子是不成立的·，这时候直接算就可以了。

剩下的，枚举每个约数 \(d\), 再算出他对每个 \(n\) 的贡献，这样复杂度可以做到 \(O(nlogn)\) 的。

Code

#include<iostream>
#include<cstdio>
#include<algorithm>
using namespace std;
#define int long long
const int N = 1e6+10;
int T,n,tot;
int prime[N],ans[N],phi[N];
bool check[N];
inline int read()
{
	int s = 0,w = 1; char ch = getchar();
	while(ch < '0' || ch > '9'){if(ch == '-') w = -1; ch = getchar();}
	while(ch >= '0' && ch <= '9'){s = s * 10 + ch - '0'; ch = getchar();}
	return s * w;
}
void YYCH()
{
	phi[1] = 1;
	for(int i = 2; i <= N-5; i++)
	{
		if(!check[i])
		{
			prime[++tot] = i;
			phi[i] = i-1;
		}
		for(int j = 1; j <= tot && i * prime[j] <= N-5; j++)
		{
			check[i * prime[j]] = 1;
			if(i % prime[j] == 0)
			{
				phi[i * prime[j]] = phi[i] * prime[j];
				break;
			}
			else phi[i * prime[j]] = phi[i] * phi[prime[j]];
		}
	}
	for(int i = 1; i <= N-5; i++)
	{
		for(int j = 2; j * i <= N-5; j++)//枚举 n = i * j， 对于 n = i 的单独算
		{
			ans[i * j] += phi[j] * j / 2;
		}
	}
}
signed main()
{
	T = read(); YYCH();
	while(T--)
	{
		n = read(); 
		if(n == 1) printf("%d\n",1);
		else printf("%lld\n",n*ans[n]+n);
	}
	return 0;
}