#创作计划#莫比乌斯全家桶

yanghongzheng

2026-02-09 08:36:09

发布于：福建

124阅读

0回复

0点赞

本人来随便学点高级数论 ~~（其实是乱翻《算法竞赛》）~~，有错轻喷。

莫比乌斯函数

$\mu(n)= \begin{cases} 1 & n=1 \\\\ (-1)^k & n\text{ 是 }k\text{ 个不同质数的乘积} \\\\ 0 & n\text{ 含有平方因子} \end{cases}$

即：

只要有 $p^2 \mid n$ ，就有 $\mu(n)=0$ 。
若 $n=p_1p_2\cdots p_k$ （ $p_i$ 都是质数且所有数互不相同），则 $\mu(n)=(-1)^k$ 。

计算

因为莫比乌斯函数是积性函数（即 $f(1) =1$ 且在 $gcd(a,b)=1$ 的情况下有 $f(a⋅b)=f(a)⋅f(b)$ ），所以可以用在 $O(n)$ 时间内预处理出所有 $[1,n]$ 内的莫比乌斯函数值。

[1] 质数的 $μ$ 为 $-1$ 。

[2] 如果一个数存在某个质因子的指数大于 $1$ ，那么它的 $μ$ 值为 $0$ 。

值得注意的是，只有当数存在最小质因子的指数大于 $1$ 时，才会被直接筛为 $0$
其他情况则由公式 $\mu(d)=-\mu(i)$ 完成，其中 $d$ 是当前数， $i$ 是某个小于 $d$ 的数

这种方法利用了积性函数的性质，使得每个数只被处理一次，从而实现线性筛。

示例 Python 代码：

maxn = int(1e6)
primes = []
mu = [0] * maxn
checkprime() # 质数筛函数，会修改 primes，太长了，这里不贴了

for i in range(1,maxn):
    mu[i] = 1

for p in primes:
    for j in range(p,maxn,p): # [1]
        mu[j] *= -1
    for j in range(p * p,maxn,p * p): # [2]
        mu[j] = 0

基础恒等式

这个式子是可以证明的，只是没那么简洁，这里不贴了，想看可以点我。

$\sum_{d\mid n} \mu(d) = \begin{cases} 1 & n=1 \\\\ 0 & n>1 \end{cases}$

莫比乌斯反演

根据上方恒等式，可推出若两个函数满足：

$g(n)=\sum_{d\mid n} f(d)$

则有：

$f(n)=\sum_{d\mid n} \mu(d)\, g\!\left(\frac{n}{d}\right)$

莫比乌斯反演例子

欧拉函数

已知：

$n = \sum_{d\mid n} \varphi(d)$

反演得：

$\varphi(n)=\sum_{d\mid n} \mu(d)\frac{n}{d}$

统计互质对数

$\sum_{i=1}^n \sum_{j=1}^n [\gcd(i,j)=1] = \sum_{d=1}^n \mu(d)\left\lfloor \frac{n}{d}\right\rfloor^2$

莫比乌斯反演例题

P2522

题目求的是 $\sum_{i=x}^n \sum_{j=y} ^m [\gcd(i,j) = k]$ ，简单的类似二维前缀和的方法优化式子，然后消掉 $k$ 变为 $\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor} [\gcd(i,j) = 1]$ 。

再变为 $\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor} \sum _{d | \gcd(i,j)} \mu(d)$ 。

接下来交换求和顺序，在上述式子中，如果 $d$ 要被枚举到，显然需要当且仅当 $d∣i$ 并且 $d∣j$ 。所以把这个部分计入到贡献当中：

$\sum_d \mu(d) \sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} [d \space | \space i] \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor } [d \space | \space j]$

最后化简：

$\sum_d\mu(d)\lfloor\dfrac{n}{dk}\rfloor\lfloor\dfrac{m}{dk}\rfloor$

但是数据太强了，直接计算过不了，所以我们可以用到积性函数的性质做前缀和用 $O(\sqrt n)$ 的复杂度求解。

MAX = int(5e4)
mu = [1] * (MAX + 1)
isp = [True] * (MAX + 1)
p = []

for i in range(2,MAX + 1): # 质数筛 + 求 μ(i)
    if isp[i]:
        p.append(i)
        mu[i] = -1
    for pr in p:
        if i * pr > MAX:
            break
        isp[i * pr] = False
        if i % pr == 0:
            mu[i * pr] = 0
            break
        mu[i * pr] = mu[i] * mu[pr] # 积性函数性质


pre = [0] * (MAX + 1)
for i in range(1,MAX + 1):
    pre[i] = pre[i-1] + mu[i] # 前缀


def f(n,m): # 最主要的计算函数
    if n == 0 or m == 0:
        return 0
    res = 0
    mn = min(n,m)
    d = 1
    while d <= mn:
        nd = min(n//(n//d),m//(m//d))
        res += (pre[nd] - pre[d-1]) * (n//d) * (m//d)
        d = nd + 1
    return res


t = int(input())
for trqlovepzh in range(t):
    a,b,c,d,k = map(int,input().split())
    n1 = b//k
    m1 = d//k
    n2 = (a-1)//k
    m2 = (c-1)//k

    ans = f(n1,m1) - f(n2,m1) - f(n1,m2) + f(n2,m2)
    print(ans)

P2257

题目求的是 $\sum_{i=x}^n \sum_{j=y} ^m [\gcd(i,j) \in \text{Prime}]$ 。

按照 P2522 的套路变为：

$\sum _{k \in \text{Prime}} \sum_d \mu(d) \lfloor \dfrac{n}{dk} \rfloor \lfloor \dfrac{m}{dk} \rfloor$

发现过不了。

观察到复杂度高的原因是双求和导致的，并且 $dk$ 重复出现了，所以可以令 $T = dk$ 。接下来，先枚举 $T$ ，显然 $T \le \min(n,m)$ 。先把后面的那个部分写下来。再考虑会有多少的 $μ()$ 会加在这个部分上。我们要让求的和的值等价不变，由于 $d = T \div k$ ，所以：

$\sum _{T=1} ^{\min(n,m)} \lfloor \dfrac{n}{T} \rfloor \lfloor \dfrac{m}{T} \rfloor \sum _{k | T,k \in \text{Prime}} \mu (\dfrac{T}{k})$

发现后面那个部分跟 $n,m$ 没有一点关系了。所以这个求和被我们优化掉了。开个数组记录一下就可以了。

注意，交换求和的意义是将东西一起计算，我们通常都会把一些相同的东西给组合到一起，这样就可以离线处理一些东西，继而达到降低时间复杂度的意义。

我的这份 Python 代码由于语言本身较慢所以是无法通过的。

MAX = int(1e7)
mu = [1] * (MAX + 1)
isp = [True] * (MAX + 1)
p = []
g = [0] * (MAX + 1)


isp[0] = isp[1] = False 
for i in range(2,MAX + 1): # 质数筛 + μ(i)
    if isp[i]:
        p.append(i)
        mu[i] = -1
    for pr in p:
        if i * pr > MAX:
            break
        isp[i * pr] = False
        if i % pr == 0:
            mu[i * pr] = 0
            break
        mu[i * pr] = mu[i] * mu[pr]


for k in p:
    for bt in range(k,MAX + 1,k):
        g[t] += mu[bt // k]

pre = [0] * (MAX + 1) # 前缀
for i in range(1,MAX + 1):
    pre[i] = pre[i - 1] + g[i]

def f(n,m): # 计算
    if n == 0 or m == 0:
        return 0
    res = 0
    mn = min(n,m)
    d = 1
    while d <= mn:
        nd = min(n // (n // d),m // (m // d))
        res += (pre[nd] - pre[d - 1]) * (n // d) * (m // d)
        d = nd + 1
    return res



t = int(input())
for trqlovepzh in range(t):
    n,m = map(int,input().split())
    print(f(n,m))

应该不会有人第一遍就发现代码里的小彩蛋。

有帮助，赞一个

去预览

0/2000

全部评论 34

yanghongzheng
@༺ཌༀཉི༒白·羊༒༃ༀད༻ @༺དༀ༒∞░∞༒ༀཌ༻（不加团） @你是不是喜欢c++ 随便 at 几个人

3天前来自北京
7
yanghongzheng
希望 pzh 和 trq 不要发现我的帖子

11小时前来自福建
5
- Xylophone
  回复
  yanghongzheng
  pzh是谁
  
  3小时前来自广东
  1
- yanghongzheng
  回复
  Xylophone
  是 @Gragher
  
  2小时前来自福建
  1
- Gragher
  回复
  Xylophone
  nm
  
  2小时前来自浙江
  2
yanghongzheng
@AC君

11小时前来自福建
3
丹尼尔
牛逼，我看不懂

2天前来自浙江
3
- shenzhangzheng
  回复
  丹尼尔
  我们是同道中人
  
  8小时前来自浙江
  2
- AK神
  回复
  shenzhangzheng
  Me either
  
  43分钟前来自江苏
  0
༺ཌༀཉི༒白·羊༒༃ༀད༻
莫比乌斯反演我居然看懂了，之前吧OIwiki看了数百遍也没看懂

24分钟前来自上海
0
一架进入异次元的波音777
666

1小时前来自上海
0
张开铭
111

1小时前来自河北
0
A380皮皮虾刘潇（飞友快关）
$\color{red}{MAN}$

1小时前来自广东
0
A380皮皮虾刘潇（飞友快关）
$\color{yellow}{MAN}$

1小时前来自广东
0
༺ཌༀ 宇智波鼬 ༀད༻
1

3小时前来自浙江
0
ACGO.Xiehao
hjh

5小时前来自广东
0
黄泽佳
HI

5小时前来自广东
0
Wa菌离我远点（郑瑞锋）

5小时前来自广东
0
Wa菌离我远点（郑瑞锋）

5小时前来自广东
0
Wa菌离我远点（郑瑞锋）

5小时前来自广东
0
ACGO.Xiehao
u

6小时前来自广东
0
ACGO.Xiehao
j

6小时前来自广东
0
ACGO.Xiehao
j

6小时前来自广东
0
ACGO.Xiehao
j

6小时前来自广东
0
ACGO.Xiehao
t

6小时前来自广东
0