【XSY2470】lcm 数学

题目大意

　　\(t\)组询问, 每组询问给定\(n\)，求\(\sum_{k=1}^n[n,k]\)，其中\([a,b]\)表示\(a\)和\(b\)的最小公倍数 .

　　\(t\leq 300000,n\leq 1000000\)

题解

\[\begin{align}
\sum_{k=1}^n[k,n]&=n\sum_{k=1}^n\frac{k}{(k,n)}\\
&=n\sum_{p|n}\frac{1}{p}\sum_{k=1}^nk[(k,n)=p]\\
&=n\sum_{p|n}\sum_{k=1}^{\lfloor\frac{n}{p}\rfloor}k[(k,\frac{n}{p})=1]\\
&=n\sum_{p|n}\frac{\frac{n}{p}\phi(\frac{n}{p})+[\frac{n}{p}=1]}{2}\\
&=n\sum_{p|n}\frac{p\phi(p)+[p=1]}{2}
\end{align}
\]

　　用线性筛或者其他方法处理出\(\phi\)函数，调和级数的复杂度预处理，每次查表。或者枚举因子。

　　时间复杂度：\(O(n\log n)\)或\(O(n+t\sqrt{n})\)

代码

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<cstdlib>

#include<ctime>

#include<utility>

#include<map>

using namespace std;

typedef long long ll;

typedef pair<int,int> pii;

int miu[1000010];

int phi[1000010];

int p[1000010];

int b[1000010];

ll e[1000010];

ll f[1000010];

int cnt;

int maxn=1000000;

map<int,ll> d;

void init()

{

	memset(b,0,sizeof b);

	int i,j;

	cnt=0;

	for(i=2;i<=maxn;i++)

	{

		if(!b[i])

		{

			p[++cnt]=i;

			miu[i]=-1;

			phi[i]=i-1;

		}

		for(j=1;j<=cnt&&i*p[j]<=maxn;j++)

		{

			b[i*p[j]]=1;

			if(i%p[j]==0)

			{

				miu[i*p[j]]=0;

				phi[i*p[j]]=phi[i]*p[j];

				break;

			}

			miu[i*p[j]]=-miu[i];

			phi[i*p[j]]=phi[i]*phi[p[j]];

		}

	}

	e[1]=1;

	for(i=2;i<=maxn;i++)

		e[i]=(ll(i)*phi[i])/2;

	for(i=1;i<=maxn;i++)

		for(j=i;j<=maxn;j+=i)

			f[j]+=e[i];

}

void solve()

{

	int n;

	scanf("%d",&n);

	printf("%lld\n",f[n]*n);

}

int main()

{

//	freopen("a.in","r",stdin);

//	freopen("a.out","w",stdout);

	init();

	int t;

	scanf("%d",&t);

	while(t--)

		solve();

	return 0;

}

巴特西

【XSY2470】lcm 数学

题目大意

题解

代码

最新文章

热门文章