莫比乌斯反演初步和实际应用
定义和一般形式及其证明
假设有数论函数关系式$F(N) = \sum_{x|N}f(x)$,则有$f(N) = \sum_{x|N}\mu(x)F(\frac Nx) = \sum_{x|N}\mu(\frac xN)F(x)$
此为基本定义,但是看到这个函数也有限制就是必须是数论函数。,也就是定义域为正整数,对应集合为复数的函数。下面是函数的一般形式。
假设d定义在$[1,∞)$上的复值函数$G(N) = \sum_{x = 1}^NF(\frac Nx)$,则有$F(N) = \sum_{x = 1}^N\mu(x)G(\frac Nx)$
而这个$\mu(x)$函数就是莫比乌斯函数,其定义如下:
$x= 1$时,$\mu(x) = 1$。
$x = P_1P_2…P_M$,($P$为互异素数),则$\mu(x) = (-1)^M$
其他情况下$\mu(x) = 0$
由定义可以得到莫比乌斯函数的两个重要性质:
对任意正整数$N$有$\sum_{x|N}\frac{\mu(x)}{x} = \frac{\varphi(N)}{N}$
证明 :
设有
代入得
由于$\sum_{x|N}\sum_{y|\frac Nx}$的限制条件为$xy|N$,所以等式写成:
证明完毕。
代码实现
用线性筛法求莫比乌斯函数,时间复杂度$O(N)$
1 | inline void Init() { |
例题:YY的GCD
给定$N, M$,求所有的$X \leq N,~Y \leq M$中$gcd(X, Y)$是质数的点对有多少对。
类似于一个模板题,因为其思维难度不是很大。考虑公式化题目描述,即求:
设$f(x)$为满足$gcd(X, Y) = X$的$(X, Y)$的对数,$F(X)$为满足$X|gcd(X, Y)$二点$(X, Y)$的对数。得到
所以根据莫比乌斯反演定理,得
而题目要求其$gcd(X,Y)$是一个质数也就是说
设$T = PX$,则式子变为
于是为了提高速度,可以预处理$\sum_{G|T}\mu(\frac TG)$。于是此题就以较快得速度解决了。
但是如果是多组数据还是有可能会$TLE$,所以如果想要更快,还可以使用整除分块。
1 |
|