51nod 1244莫比乌斯函数之和(杜教筛)

传送门

题意：

求$\sum_{i=a}^{b}\mu{(i)}$

题解：

这题就是求积性函数前缀和，一道杜教筛的模板题。
公式推导如下：
假设$\phi{(n)}=\sum_{i=1}^{n}\mu{(i)}$
我们知道有

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

我们可以把上面的公式变成这样

$$\sum_{i=1}^{n}{\sum_{j|i}{\mu{(j)}}}=1$$

然后和式变换一下($i$变成$\frac{i}{d}$)

$$\sum_{i=1}^{n}{\sum_{j=1}^{\lfloor{\frac{n}{i}}\rfloor}{\mu{(j)}}}=1$$

$$\sum_{i=1}^{n}{\phi{(\lfloor{\frac{n}{i}}\rfloor)}}=1$$

然后构造一下

$$\phi{(n)}=1-\sum_{i=2}^{n}{\phi{(\lfloor{\frac{n}{i}}\rfloor)}}$$

这样我们在$O(n^{\frac{3}{4}})$时间内算出答案啦

代码：

#include<bits/stdc++.h>
using namespace std;
const int maxn=5e6+5;
int mu[maxn],a[maxn];
map<long long,long long>b;
bool isprime[maxn];
int prime[maxn],X;
void Mu()
{
	X=5e6;
	memset(isprime,1,sizeof(isprime));
	mu[1]=1;a[1]=1;
	int temp=0;
	for(int i=2;i<maxn;i++)
	{
		if(isprime[i]) prime[++temp]=i,mu[i]=-1;
		for(int j=1;j<=temp&&prime[j]*i<maxn;j++)
		{
			isprime[i*prime[j]]=0;
			if(i%prime[j]==0)
			{
				mu[i*prime[j]]=0;
				break;
			}
			else mu[i*prime[j]]=-mu[i];
		}
		a[i]=a[i-1]+mu[i];
	 } 
 } 
 int n;
long long sumMu(long long m)
{
	if(m<=X) return a[m];
	if(b[m]) return b[m];
	long long s=0;
	for(long long i=2,j;i<=m;i=j+1)//分块优化 
	{
		j=m/(m/i);
		s+=(j-i+1)*sumMu(m/i);
	}
	b[m]=1-s;
	return b[m];
}
int main()
{
	int T,i,j,k;
	long long n,m;
	Mu();
	scanf("%lld%lld",&n,&m);
	printf("%lld\n",sumMu(m)-sumMu(n-1)); 
}

Q.E.D.