莫比乌斯函数

宝塔服务器面板，一键全能部署及管理，送你10850元礼包，点我领取

莫比乌斯函数(Möbius)

定义

定义莫比乌斯函数 (μ(x), xin N^+) ：

当 (x=p_1^{d_1}cdot p_2^{d_2}cdots p_k^{d_k}) (唯一分解定理) 时，有：

[μ(x)=
egin{cases}
0 & exists d_i>1
1 & k ext{是偶数}
-1 & k ext{是奇数}
end{cases}
]

显然，这是个数论函数。

性质

(n
e 0)时，(n) 的所有因子的莫比乌斯函数值和为 (0)

[sum_{d|n}mu (x)=
egin{cases}
1 & n=1
0 & n>1
end{cases}]

证明：

(n=1) 时显然成立。

(n>1) 时有：

[n=p_1^{d_1}cdot p_2^{d_2}cdots p_k^{d_k}
]

[ecause mu (d)
e 0 Rightarrow d=p_1p_2 p_3 cdots p_t
]

[ ext{故质因子个数为r的因子只有$C_k^r$个}
]

[ herefore sum_{d|n}mu (x)=C_k^0-C_k^1+C_k^2+cdots+(-1)^kC_k^k=sum_{i=0}^k(-1)^iC_k^i
]

[ecause (x+y)^n=sum_{i=0}^nC_n^ix^iy^{n-i} ext{(二项式定理)}
]

[ ext{将$x=1,y=-1$代入得证：} sum_{i=0}^n(-1)^nC_n^i=0
]

莫比乌斯函数是积性函数

对任意 (n in Z^+) 有：

[sum_{d|n} frac{mu (d)}{d}=frac{varphi(n)}{n}
]

代入莫比乌斯反演公式 ~~(我也不会)~~ 即可。

应用

这个函数可用来解决如下问题：

与某个数 (N) 互质的数的个数：

设 (S_p) 表示(1 – n) 中 (p) 的倍数的个数。

则根据容斥原理，所求转化为如下式子：(N-S_2-S_3-cdots +S_{2,3}+S_{2,5}+cdots -S_{2,3,5}cdots)

通过观察，每一个 (S) 代表的集合的数的莫比乌斯函数就是这个 (S) 的系数。

莫比乌斯函数可以利用筛法求出。

例题：破译密码

达达正在破解一段密码，他需要回答很多类似的问题：

对于给定的整数(a,b)和(d)，有多少正整数对(x,y)，满足(x<=a，y<=b)，并且(gcd(x,y)=d)。

作为达达的同学，达达希望得到你的帮助。

输入格式

第一行包含一个正整数 (n) ，表示一共有n组询问。

接下来 (n) 行，每行表示一个询问，每行三个正整数，分别为 (a,b,d) 。

输出格式

对于每组询问，输出一个正整数，表示满足条件的整数对数。

数据范围

(1≤n≤50000,
1≤d≤a,b≤50000)

解析

考虑对于每一个询问如何做。

对于一组(1leq xleq a,1le yle b)

(gcd(x,y)=dRightarrow gcd(x^{prime},y^{prime})=1)
其中 (x^{prime}=frac{x}{d} , y^{prime}=frac{y}{d} , x^{prime}in[1,lfloorfrac{a}{d}floor],y^{prime}in[1,lfloorfrac{b}{d}floor])

问题转化为：有多少对 (x^{prime},y^{prime}) 互质。

可以考虑容斥定理：

[Ans=a^{prime}b^{prime}-lfloorfrac{a^{prime}}{2}floorlfloorfrac{b^{prime}}{2}floor+lfloorfrac{a^{prime}}{3}floorlfloorfrac{b^{prime}}{3}floor-lfloorfrac{a^{prime}}{5}floorlfloorfrac{b^{prime}}{5}floorcdots+lfloorfrac{a^{prime}}{6}floorlfloorfrac{b^{prime}}{6}floor+cdots
]

记 (lfloorfrac{a^{prime}}{i}floorlfloorfrac{b^{prime}}{i}floor=S_i)

上面的式子很熟悉了，我们还可以继续化得下面的式子：

[Ans=sum_{i=1}^{min(a^{prime},b^{prime})}lfloorfrac{a^{prime}}{i}floorlfloorfrac{b^{prime}}{i}floorcdotmu (i)
]

直接做的话是 (O(n^2)) 的。

考虑对于 (lfloorfrac{a^{prime}}{i}floor) ，有 (lfloorfrac{a^{prime}}{1}floor，lfloorfrac{a^{prime}}{2}floor，cdots ，lfloorfrac{a^{prime}}{a^{prime}}floor) 共 (a^{prime}) 项，但是不同的数只有 (2sqrt{a^{prime}}) 个。于是可以考虑 (O(sqrt{n})) 分块 , 复杂度变为 (O(nsqrt{n})) 可以接受。

下面解释一下为什么只有 (2sqrt{a^{prime}}) 个分段：

令 (A(x)=lfloorfrac{a^{prime}}{x}floor)

将序列分为两部分：(A(1) sim A(sqrt{a^{prime}}) , A(sqrt{a^{prime}}+1) sim A(a^{prime}))

对于左边，显然有且只有 (sqrt{n}) 个取值。

对于右边，观察得知分母是恒大于 (sqrt{a^{prime}}) 的，则整个项的值是恒小于 (sqrt{a^{prime}}) 的，总共 (sqrt{a^{prime}}) 个不同取值。

两边相加，得证。

然后是另外一个问题，怎么去求每一段。

这里定义：(g(x)) 为 (lfloorfrac{a^{prime}}{x}floor=k) 时 (x) 能够取到的最大整数。

即 (lfloorfrac{a^{prime}}{x}floor=lfloorfrac{a^{prime}}{g(x)}floor) 且 (lfloorfrac{a^{prime}}{x}floor > lfloorfrac{a^{prime}}{g(x)+1}floor)

对于这个函数有这样一个很经典的公式 (g(x)=Biglfloorfrac{a^{prime}}{lfloorfrac{a^{prime}}{x}floor}Bigfloor)

这其实就是整除分块，在数论这一章我们将经常遇到。

下面给出正确性证明(下面的 (a) 其实是上面的 (a^{prime}))：

[ecause g(x)=Biglfloorfrac{a}{lfloorfrac{a}{x}floor}Bigfloor
]

[ herefore g(x) geq Biglfloorfrac{a}{frac{a}{x}}Bigfloor = x
]

[ herefore lfloor frac{a}{g(x)} floor leq lfloor frac{a}{x} floor
]

[ecause Bigglfloor frac{a}{frac{a}{lfloorfrac{a}{x}floor}} Biggfloor geq lfloor frac{a}{x} floorRightarrow Bigglfloor frac{a}{Biglfloorfrac{a}{lfloorfrac{a}{x}floor}Bigfloor} Biggfloor geq lfloor frac{a}{x} floor
]

[ herefore lfloor frac{a}{g(x)} floor geq lfloor frac{a}{x} floor
]

[ ext{故 $lfloor frac{a}{g(x)} floor = lfloor frac{a}{x} floor$ 成立}
]

[ ext{设 $a=kx+r , 0leq r leq x$ (带余除法)}
]

[ ext{代入 $lfloorfrac{a}{x}floor > lfloorfrac{a}{g(x)+1}floor$ 得：} k>Biglfloorfrac{a}{lfloorfrac{a}{k}floor+1}Bigfloor
]

[k(lfloorfrac{a}{k}floor+1)>a
]

[ ext{再设$a=pk+q,0leq q < k$}
]

[ ext{代入得：} k(p+1)>pk+qRightarrow k>q, ext{满足要求}
]

[ ext{故 $lfloorfrac{a}{x}floor > lfloorfrac{a}{g(x)+1}floor$ 成立}
]

有了这个结果，整个问题就简单多了。

code：

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N=5e4+10;

int primes[N],cnt;
bool mp[N];
int mob[N],sum_[N];//莫比乌斯函数，前缀和

void init(int n)//线筛求莫比乌斯函数
{
	mob[1]=1;
	for(int i=2; i<=n; i++)
	{
		if(!mp[i])
		{
			primes[cnt++]=i;
			mob[i]=-1;//质数有两个一次质因子
		}
		for(int j=0; primes[j]*i<=n; j++)
		{
			int tmp=primes[j]*i;
			mp[tmp]=1;
			if(i%primes[j]==0)
			{
				mob[tmp]=0;//tmp有二次质因子
				break;
			}
			mob[tmp]=mob[i]*-1;//多了一个质因子
		}
	}

	for(int i=1; i<=n; i++) //前缀和
	{
		sum_[i]=sum_[i-1]+mob[i];
	}
}

int main()
{
	init(5e4);

	int n;
	scanf("%d",&n);
	for(int i=1; i<=n; i++)
	{
		int a,b,d;
		scanf("%d%d%d",&a,&b,&d);
		a/=d,b/=d;//问题转化
		int mina=min(a,b);

		ll res=0;
		for(int l=1,r; l<=mina; l=r+1) //分块
		{
			r=min(mina,min(a/(a/l),b/(b/l)));//每次只往后面跳一个较小的值
			res+=(sum_[r]-sum_[l-1])*(ll)(a/l)*(b/l);//核心式子
		}

		printf("%lld
",res);
	}
	return 0;
}

莫比乌斯函数