bzoj 3944: Sum【莫比乌斯函数+欧拉函数+杜教筛】

一道杜教筛的板子题。

两个都是积性函数，所以做法是一样的。以mu为例，设\( f(n)=\sum_{d|n}\mu(d) g(n)=\sum_{i=1}^{n}f(i) s(n)=\sum_{i=1}^{n}\mu(i) \)，然后很显然对于mu\( g(n)=1\)，对于phi\( g(n)=n*(n+1)/2 \)，然后可以这样转化一下：

\[g(n)=\sum_{i=1}^{n}\sum_{d|n}\mu(d)
\]

\[=\sum_{d=1}^{n}\mu(d)\left \lfloor \frac{n}{d} \right \rfloor
\]

\[=\sum_{d=1}^{n}s(\left \lfloor \frac{n}{d} \right \rfloor)
\]

\[s(n)=g(n)-\sum_{d=2}^{n}s(\left \lfloor \frac{n}{d} \right \rfloor)
\]

然后递归求解子问题即可。

时间复杂度据说是预处理三分之二的部分加上记忆化可以到\( O(n^{\frac{2}{3}}) \)。当然我并不会算……

p.s 因为是分块来做，所以没必要用map来记忆化。因为预处理了三分之二的部分，所以需要递归计算的x一定大于\( n^{\frac{2}{3}} \)，这意味着\( \frac{n}{x} \)的数组取值在可接受的范围之内，事实上，这个数组往往非常小，并且因为分块，所以同一个下标上存的是同一个块的答案，不会冲突。（然而我跑的和map一样慢是怎么回事……

#include<iostream>

#include<cstdio>

#include<cstring>

using namespace std;

const int N=5000005,m=5000000;

int T,n,tot,q[N];

long long phi[N],mb[N],hphi[5005],hmb[5005];

bool v[N],vmb[5005],vphi[5005];

long long wkmb(long long x)

{

	if(x<=m)

		return mb[x];

	if(vmb[n/x])

		return hmb[n/x];

	vmb[n/x]=1;

	long long re=1ll;

	for(long long i=2,la;i<=x;i=la+1)

	{

		la=x/(x/i);

		re-=(long long)(la-i+1)*wkmb(x/i);

	}

	return hmb[n/x]=re;

}

long long wkphi(long long x)

{

	if(x<=m)

		return phi[x];

	if(vphi[n/x])

		return hphi[n/x];

	vphi[n/x]=1;

	long long re=(long long)x*(x+1)/2;

	for(long long i=2,la;i<=x;i=la+1)

	{

		la=x/(x/i);

		re-=(long long)(la-i+1)*wkphi(x/i);

	}

	return hphi[n/x]=re;

}

int main()

{

	phi[1]=mb[1]=1;

	for(int i=2;i<=m;i++)

	{

		if(!v[i])

		{

			q[++tot]=i;

			mb[i]=-1;

			phi[i]=i-1;

		}

		for(int j=1;j<=tot&&i*q[j]<=m;j++)

		{

			long long k=i*q[j];

			v[k]=1;

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

			{

				mb[k]=0;

				phi[k]=phi[i]*q[j];

				break;

			}

			mb[k]=-mb[i];

			phi[k]=phi[i]*(q[j]-1);

		}

	}

	for(int i=1;i<=m;i++)

	{

		phi[i]+=phi[i-1];

		mb[i]+=mb[i-1];

	}

	scanf("%lld",&T);

	while(T--)

	{

		memset(vmb,0,sizeof(vmb));

		memset(vphi,0,sizeof(vphi));

		scanf("%lld",&n);

		printf("%lld %lld\n",wkphi(n),wkmb(n));

	}

	return 0;

}

巴特西

bzoj 3944: Sum【莫比乌斯函数+欧拉函数+杜教筛】

最新文章

热门文章