莫比乌斯函数:d=1,μ(d)=1; d=\prod_{i=1}^{k}{p}_{i}, 即d的质因子中没有重复的,μ(d)=(-1)^k; 否则μ(d)=0

莫比乌斯函数的线性求法:

void Mobius(){
    mu[1] = 1, cnt = 0, vis[1] = 1;
    for (ll i=2; i<=n; i++){
        if (!vis[i])    prime[++cnt] = i, mu[i] = -1;
        for (int j=1; j<=cnt && i*prime[j]<=n; j++){
            vis[i*prime[j]] = 1;
            if (i%prime[j]==0)  break;
            else   mu[i*prime[j]] = -mu[i];
        }
    }
    for (int i=1; i<=n; i++)    mu[i] += mu[i-1];
}

莫比乌斯反演

莫比乌斯反演是数论中重要且比较难的一部分,对于一些函数f(n),当很难直接求出它的值,而很容易求出它的约数或者倍数和时,可以通过莫比乌斯反演简化运算,求得f(n)。(其实这块主要就是推式子...)

本文章讨论莫比乌斯反演的所有前置内容以及莫比乌斯反演的一般套路,还有相关的一些例题。


几个常用到的公式

莫比乌斯函数
d = 1时,μ(d)=1;
d为k个只出现1次的质数相乘时,μ(d)=(-1)^k
对于其它情况,μ(d) = 0.
莫比乌斯函数是积性函数。

积性函数

若函数f(x)满足当gcd(a, b)=1时有f(ab) = f(a)f(b),则f(x)为积性函数。
若函数f(x)满足对任意正整数a, b有f(ab) = f(a)f(b),则f(x)为完全积性函数。

任何一个积性函数都可以线性筛出来,就像欧拉函数,莫比乌斯函数一样。

单位函数,也叫狄利克雷单位元,\varepsilon(x) = [x=1],emm在平面上就是一个点。(完全积性函数)

常数函数I(x) = 1。 (完全积性函数)

恒等函数id(x) = x。(完全积性函数)

欧拉函数
x的欧拉函数\phi(x)的值为在[1, x-1]中,有多少个数和x互素。
\phi(x) = x\prod(1-\frac{1}{Pi}),Pi为x的质因数。一个质因数只计算一次。
欧拉函数是积性函数。
线性求欧拉函数:

void getEular(){
    mu[1] = 1, cnt = 0, vis[1] = 1;
    for (ll i=2; i<=n; i++){
        if (!vis[i])    prime[++cnt] = i, mu[i] = -1, eular[i] = i-1;
        for (int j=1; j<=cnt && i*prime[j]<=n; j++){
            vis[i*prime[j]] = 1;
            if (i%prime[j]==0) {
                eular[i*prime[j]] = eular[i]*prime[j];
                break;
            }else   mu[i*prime[j]] = -mu[i], eular[i*prime[j]] = eular[i]*eular[prime[j]];
        }
    }
    for (int i=1; i<=n; i++)    mu[i] += mu[i-1];
}

对于i%prime[j]==0这种情况的证明,因为prime[j]是i最小的质因数。我们根据唯一分解定理把i表示成n=\prod_{i=1}^{m}p_{i}^{q_{i}}的形式,然后开始推算:\phi(n) = \prod_{i=1}^{m}\phi(p_{i}^{q_{i}}) = \prod_{i=1}^{m}p_{i}^{q_{i}} - p_{i}^{q_{i}-1}(不与p_{i}^{q_{i}}互质的只有p_i的倍数,有p_i^{q_i-1}个) = \prod_{i=1}^{m}p_{i}^{q_{i-1}}(p_i-1),根据上式,某个质因数的幂多一次,n的欧拉函数值就会乘以这个质因数,证毕。
按照上述思路,可以用线性筛求得一类积性函数,即主要从3个步骤来求。假设要求积性函数f(x)
第①步:当x为质数时,直接求;
第②步:当x为非质数时,可以把x表示成x=i*prime[j]的形式,,prime[j]是x的最小质因子。若i%prime[j]==0,说明i的最小质因子也是prime[j],此时根据唯一分解定理:f(x)=f(\prod p_i^{q_i}) = \prod f(p_i^{q_i}),相当于在i的最小质因子的幂上多了1,讨论分析此时f(x)的值为何。这一步通常来说是比较麻烦的一步。
第③步:在②中,当i%prime[j]!=0时,gcd(i, prime[j])=1,i没有prime[j]这个质因子,根据积数函数性质有f(x) = f(i)*f(prime[j])

数论分块

对于一个整数n,n除以[1,n]内的所有整数d向下取整,总共有2\sqrt(n)种取值。

对于d<=\sqrt(n)\lfloor \frac{n}{d} \rfloor共有\sqrt(n)种取值;
对于d>=\sqrt(n)\lfloor \frac{n}{d} \rfloor共有\sqrt(n)种取值。

对于一个数d,n除以区间[d, \lfloor \frac{n}{\lfloor \frac{n}{d} \rfloor} \rfloor]内的数向下取整得到的值结果都是一样的。

狄利克雷卷积

设f,g是两个函数,它们的狄利克雷卷积是(f*g)(n) = \sum_{d|n} f(d)g(\frac{n}{d}),就是n的约数对分别取f,g函数相乘在相加就行了。

狄利克雷卷积满足交换律,结合律。

并且在用到的最多的几个函数中有如下性质:
\phi * I = id
\mu * I = \varepsilon
\mu * id = \phi

一定要熟记这些个函数:\phi, \mu, ... \varepsilon, I, id

莫比乌斯反演公式

f(n), F(n)为两个数论公式。
如果有F(n) = \sum_{n|d}f(d),d为n的倍数,则有f(n) = \sum_{n|d} \mu(\frac{d}{n}) F(d)
如果有F(n) = \sum_{d|n}f(d),d为n的约数,则有f(n) = \sum_{d|n} \mu(\frac{n}{d}) F(d)

这两个公式的理论支持是:\mu * I = \varepsilon

在以上理论基础上,莫比乌斯反演的题目一般都是经过一系列推式子之后,可以先线性或非线性预处理,然后在可以分块在sqrt(n)时间复杂度内解决单个测试样例。一般难点是推式子和预处理。

总结的性质

\phi(ij) = \frac{\phi(i) \phi(j) gcd(i, j)}{\phi(gcd(i,j))},特殊的,当j为i的因子时,\phi(ij) = j\phi(i),这个性质可以用唯一分解定理和积性函数的性质很容易得到。
d(ij) = \sum_{x|i} \sum_{y|j}[gcd(x, y)=1]约数个数函数分解。
一般的简单题目推到最后就是分块+积性函数求和问题,积性函数要么线筛,要么直接nlnn,要么就是范围比较大,用杜教筛求前缀;也可能是分块搭配一些不能直接求的函数,需要推导来求其前缀和。当然还有更难的不会做...

下面推几个比较经典的式子,套路就在里面。。

推演1

推演1

推演2

推演2

推演3

推演3

推演4

推演4

推演5

推演5

推演6

推演6

题目

余数求和
模积和
GCD SUM
GCD
GCD - Extreme (I)
GCD - Extreme (II)
于神之怒加强版
[国家集训队]Crash的数字表格 / JZPTAB
[SDOI2015]约数个数和
[SDOI2017]数字表格
[]()
[]()
[]()
[]()
[]()
[]()
[]()
[]()
[]()


0 条评论

发表评论

邮箱地址不会被公开。