引入
求1−1000以内不能被2、3、5整除的数的个数。
经典的容斥题目,上来先甩一个柿子:ans=1000−[10002]−[10003]−[10005]+[10002×3]+[10002×5]+[10003×5]−[10002×3×5]([]表示高斯取整)(容斥没有不会的吧,不会的请回算法基础课重造谢谢)
但是我们发现一个问题:容斥在写的时候容易将正负号弄反,所以我们发明了莫比乌斯函数:μ(N)
莫比乌斯函数
设N=∏ki=1pαii(p1,p2,p3…为质数数列)
μ(N)={1,N=1 (−1)k,α1=α2=⋯=αk=1 0,存在至少一个αi>1也就是含有平方因子
那这个莫比乌斯函数有啥用呢?表面上看这个函数就是在扯,但是我们会发现一件事情:μ(2)=−1,μ(3)=−1,μ(5)=−1,μ(2×3)=1…,我们发现μ(k)就是[1000k]前的系数,所以下次写容斥的时候就不会写错了(但是这种方法只能用在为质数的情况,例如:2,3,5就为质数,故可以用莫比乌斯函数表示系数)
性质
莫比乌斯函数为积性函数(若函数f(x)满足当gcd(a,b)=1时f(ab)=f(a)×f(b),则函数f(x)为积性函数),证明如下(巨佬们可自行跳过):
若已知a,b,且(a,b)=1,则μ(ab)为:
- a=1,则μ(ab)=μ(b)×1=μ(b)×μ(a)
- b=1,则μ(ab)=μ(a)×1=μ(a)×μ(b)
- μ(a)=0或μ(b)=0,那么ab中也有平方因子,所以μ(ab)=0,则μ(ab)=μ(a)×μ(b)
- 设a=∏kai=1pαiia,b=∏kbi=1pβiib,则μ(a)=(−1)ka,μ(b)=(−1)kb,又因为(a,b)=1,所以μ(ab)=(−1)ka+kb=(−1)ka×(−1)kb=μ(a)×μ(b)
莫比乌斯反演
啥都别讲,直接给出一个逝子F(N)=∑d|Nf(d)⇔f(N)=∑d|nμ(d)F(nd)
是不是懵了😵
那这个式子具体是啥意思呢?让我们看一下具体的描述:设F(N)和f(N)是定义在正整数集合上的两个函数,定义如下。
若F(N)函数满足:
F(N)=∑d|Nf(d)
则有
f(N)=∑d|Nμ(d)F(Nd)
那如何证明呢?事实上这个的证法要用迪利克雷卷积(其实还是本人太菜了,想不出别的又快又简洁又严谨的证法),而那个就是大学内容了,暂时不讲如何证明了,而且记下来莫比乌斯反演也挺简单的。
举例
我们可以举一个关于欧拉函数(φ(N))的例子,令f(N)=φ(N)。
设N=k∏i=1pαii φ(N) =N×k∏i=1pi−1pi =N×(1−1p1)×(1−1p2)…(1−1pk) =N−Np1−Np2−⋯−Npk+Np1×p2+Np1×p3+… =∑d|Nμ(d)(Nd)则可以令F(N)=N,那么就能得到N=∑d|Nφ(d)
那么N=∑d|Nφ(d)到底对不对呢?证明如下:
Proof
记所有在1−N内的i满足(i,N)=k的i的个数为C(N,k)
显然C(N,1)=φ(N)
\because (i,N)=k \Leftrightarrow (\frac{i}{k},\frac{N}{k})=1
\therefore C(N,k)=C(\frac{N}{k},1)=\varphi(\frac{N}{k})
又\because N=\sum_{d|N}{C(N,d)}(对(i,N)的取值进行分类)
\therefore N=\sum_{d|N}\varphi(\frac{N}{d})=\sum_{d|N}\varphi(d)
证毕!
重点题目
例题一:洛谷P1390
莫比乌斯反演其实不难,唯一的难点在于寻找F与f。
题目要求\sum_{i=1}^n \sum_{j=i+1}^n gcd(i,j),可以换个写法:设f(d)表示满足gcd(i,j)=d的数对(i,j)的数量,则\sum_{i=1}^n \sum_{j=i+1}^n gcd(i,j) = \sum_{d=1}^n{d \times [(f(d)-1)\div 2]}(还有i<j这个条件,所以要减1再除2),所以现在只要在可接受的时间复杂度内求出f(d)就可以了。
但是f(d)其实也不好求,于是一个经典思路就出现了:设F(d)表示表示满足d|gcd(i,j)的数对(i,j)的数量。
这个F(d)就好求了,为(n\div d)^2(想一想,为什么),那么如何用F(d)求f(d)呢?
考虑容斥,先将F(d)加进来,再减去公因数为2d的倍数的个数,也就是减去F(2d),减去公因数为2d的倍数的个数,公因数为6d的倍数的个数减了两次要再加上\dots那么跟开头一样,f(d)=F(d)-F(2d)-F(3d)+F(6d)\dots=\sum_{i=1}^{\frac{n}{i}}\mu(i)F(id)
时间复杂度
O(\frac{1}{n}+\frac{2}{n}+\dots+\frac{n}{n})=O(nln n)
参考代码
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n;
LL p[2000010],t,mo[2000010];//mo[i]:莫比乌斯函数
bool st[2000010];
void get_prime(LL x)//线性筛筛积性函数,大佬们用的一般是杜教筛,但本蒟蒻不会
{
st[0]=st[1]=1;
mo[1]=1;
for(LL i=2;i<=x;i++){
if(!st[i])p[++t]=i,mo[i]=-1;
for(LL j=1;p[j]<=x/i;j++){
st[i*p[j]]=1;
if(i%p[j]==0){
mo[i*p[j]]=0;
break;
}
mo[i*p[j]]=mo[i]*mo[p[j]];
}
}
}
LL F(LL x)
{
return (n/x)*(n/x);
}
int main()
{
LL i,j,ans=0;
cin>>n;
get_prime(n);
for(i=1;i<=n;i++){
LL c=0;
for(j=1;j<=n/i;j++)c+=mo[j]*F(j*i);
ans+=(c-1)/2*i;
}
cout<<ans;
}
例题二 洛谷P2522/AcWing 2702
直接参照例题一的思路,gcd(i,j)=k不好求就求k|gcd(i,j),但是这题有下界,于是我们有一个前缀和(理解为容斥也行)思路:设sol(a,b)为满足1≤i≤a且1≤j≤b且gcd(i,j)=k的数对(i,j)的个数,则答案为sol(b,d)-sol(a-1,d)-sol(b,c-1)+sol(a-1,c-1)。
于是就能写出代码了(抄袭党来此处复制🙃)
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,k;
int p[50010],t,mo[50010];
bool st[50010];
void get_prime(int x)
{
st[0]=st[1]=1,mo[1]=1;
for(int i=2;i<=x;i++){
if(!st[i])p[++t]=i,mo[i]=-1;
for(int j=1;p[j]<=x/i;j++){
st[i*p[j]]=1;
if(i%p[j]==0){
mo[i*p[j]]=0;
break;
}
mo[i*p[j]]=mo[p[j]]*mo[i];
}
}
}
int sol(int b,int d)
{
int s=0,i;
for(i=1;i<=min(b,d);i++)s+=mo[i]*(b/i)*(d/i);
return s;
}
int main()
{
int t,i;
cin>>t;
get_prime(50000);
while(t--){
cin>>a>>b>>c>>d>>k;
cout<<sol(b/k,d/k)-sol((a-1)/k,d/k)-sol(b/k,(c-1)/k)+sol((a-1)/k,(c-1)/k)<<endl;
}
}
结果发现TLE了,只得了30,why?
观察下数据范围,n为50000,k最小为1,a,b,c,d的最大值为50000,也就是最高会达到50000 \times 50000,妥妥的超时。
那如何优化呢?观察F函数,是用[\frac{b}{i}]与[\frac{d}{i}]组成的,看到这两个我们会想起什么?对了,就是二维数论分块,对b,d数论分块可将复杂度降至根号级别。
AC Code:
#include<bits/stdc++.h>
using namespace std;
int a,b,c,d,k;
int p[50010],t,mo[50010],sum[50010];
bool st[50010];
void get_prime(int x)
{
st[0]=st[1]=1,mo[1]=1;
for(int i=2;i<=x;i++){
if(!st[i])p[++t]=i,mo[i]=-1;
for(int j=1;p[j]<=x/i;j++){
st[i*p[j]]=1;
if(i%p[j]==0){
mo[i*p[j]]=0;
break;
}
mo[i*p[j]]=mo[p[j]]*mo[i];
}
}
for(int i=1;i<=x;i++)sum[i]=sum[i-1]+mo[i];
}
int sol(int b,int d)
{
int s=0,l=1,r1,r2,r;
while(l<=min(b,d)){//二维数论分块
r1=b/(b/l);
r2=d/(d/l);
r=min(r1,r2);
s+=(sum[r]-sum[l-1])*(b/r)*(d/r);
l=r+1;
}
return s;
}
int main()
{
int t,i;
cin>>t;
get_prime(50000);
while(t--){
cin>>a>>b>>c>>d>>k;
cout<<sol(b/k,d/k)-sol((a-1)/k,d/k)-sol(b/k,(c-1)/k)+sol((a-1)/k,(c-1)/k)<<endl;
}
}
难题
洛谷P2231/AcWing.2098
当然,这题可以用DP,但是我们来讲一个莫比乌斯反演的做法。
设卡片上的数为x_1,x_2 \dots x_{n+1},则此卡片满足要求的充分必要条件为存在一组数a_1,a_2 \dots a_{n+1},使得a_1 x_1 + a_2 x_2 + \dots a_{n+1} x_{n+1} = 1,由裴蜀定理易得充分必要条件等价于gcd(x_1,x_2 \dots x_{n+1}) = 1。
而公约数为1是极困难的,考虑正难则反。
设gcd(x_1,x_2 \dots x_{n+1}) = d,又\because x_{n+1}=m,\therefore d|m,因此可以枚举d,所以答案就不难写出:
m^n+\sum_{d|m,d>1} \mu(d)(\frac{m}{d})^n \\\
=\sum_{d|m} \mu(d)(\frac{m}{d})^n \\\
=m^n*\sum_{d|m} \mu(d)\frac{1}{d^n} \\\
令m=\prod_{i=1}^k {p_i}^{\alpha_i}. \\\
答案=m^n * \prod_{i=1}^k (1-\frac{1}{p_i^n})
代码自行实现
Code:
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
LL n,m;
LL qmi(LL a,LL b)
{
LL ans=1;
while(b){
if(b&1)ans=ans*a;
a=a*a;
b>>=1;
}
return ans;
}
int main()
{
LL i;
cin>>n>>m;
LL ans=qmi(m,n);
for(i=2;i<=m/i;i++)
if(m%i==0){
LL s=qmi(i,n);
ans/=s,ans*=s-1;
while(m%i==0)m/=i;
}
if(m>1){
LL s=qmi(m,n);
ans/=s,ans*=s-1;
}
cout<<ans;
}
加道难题刑,等我把坑填完