莫比乌斯反演
μ(1)=1 μ(2)=−1 μ(3)=−1 μ(4)=0 ……
定义如下：
1. μ(1)=1
2. 当x 分解质因数后，所有质因数的指数为1，那么 μ(x)=(−1) k (k为将x 分解质
因数后，质因数的个数）
3.
当x 分解质因数后，有质因数的指数>1，那么 μ(x)=0 （为什么这样定义自行理解（有点容斥））
莫比乌斯函数的重要性质：
=0(n>1)或1(n=1)
证明：将n
分解
根据定义，只有在k 个p 里取，每个p 指数为1时才有效，取奇数个为-1，去偶数个为1
积性函数：μ(xy)=μ(x)μ(y)
所以可以用线性筛的方法筛出莫比乌斯函数：
mu[1]=1;
for (i =2; i
if(!not_prime[i])
{
prime[++tot]=i;
mu[i]=-1;
}
for (j =1;prime[j]*i
{
not_prime[prime[j]*i]=1;
if(i%prime[j]==0)
{
mu[prime[j]*i]=0;
break;
}
mu[prime[j]*i ]=-mu[i];
}
}
现在倒回来证明开始那个反演函数：
实际题目中，直接跑莫比乌斯反演暴力一般是要超时的。。。一般都要加优化。主要有一个分块思想。
if (n>m)
swap(n,m);
for (i =1; i
{
last=min(n/(n/i),m/(m/i));
re+=(n/i)*(m/i)*(sum[last]-sum[i-1]);
}
return re;
莫比乌斯反演
μ(1)=1 μ(2)=−1 μ(3)=−1 μ(4)=0 ……
定义如下：
1. μ(1)=1
2. 当x 分解质因数后，所有质因数的指数为1，那么 μ(x)=(−1) k (k为将x 分解质
因数后，质因数的个数）
3.
当x 分解质因数后，有质因数的指数>1，那么 μ(x)=0 （为什么这样定义自行理解（有点容斥））
莫比乌斯函数的重要性质：
=0(n>1)或1(n=1)
证明：将n
分解
根据定义，只有在k 个p 里取，每个p 指数为1时才有效，取奇数个为-1，去偶数个为1
积性函数：μ(xy)=μ(x)μ(y)
所以可以用线性筛的方法筛出莫比乌斯函数：
mu[1]=1;
for (i =2; i
if(!not_prime[i])
{
prime[++tot]=i;
mu[i]=-1;
}
for (j =1;prime[j]*i
{
not_prime[prime[j]*i]=1;
if(i%prime[j]==0)
{
mu[prime[j]*i]=0;
break;
}
mu[prime[j]*i ]=-mu[i];
}
}
现在倒回来证明开始那个反演函数：
实际题目中，直接跑莫比乌斯反演暴力一般是要超时的。。。一般都要加优化。主要有一个分块思想。
if (n>m)
swap(n,m);
for (i =1; i
{
last=min(n/(n/i),m/(m/i));
re+=(n/i)*(m/i)*(sum[last]-sum[i-1]);
}
return re;