#创作计划#莫比乌斯反演

userId_undefined
yanghongzheng
时空双修者8月全勤卷王出道萌新USACO荣耀黄金

2026-02-11 09:15:44

发布于：福建

332阅读
0回复
0点赞

头图

补充说明左边是一个同班的（五年级）同学 @你好。

正文

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

莫比乌斯函数

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

即：

  • 只要有 p2∣np^2 \mid n，就有 μ(n)=0\mu(n)=0。
  • 若 n=p1p2⋯pkn=p_1p_2\cdots p_k（pip_i 都是质数且所有数互不相同），则 μ(n)=(−1)k\mu(n)=(-1)^k。

计算

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

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

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

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

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

示例 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

基础恒等式

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

∑d∣nμ(d)={1n=10n>1\sum_{d\mid n} \mu(d) = \begin{cases} 1 & n=1 \\\\ 0 & n>1 \end{cases}

莫比乌斯反演

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

g(n)=∑d∣nf(d)g(n)=\sum_{d\mid n} f(d)

则有：

f(n)=∑d∣nμ(d) g ⁣(nd)f(n)=\sum_{d\mid n} \mu(d)\, g\!\left(\frac{n}{d}\right)

莫比乌斯反演例子

欧拉函数

已知：

n=∑d∣nφ(d)n = \sum_{d\mid n} \varphi(d)

反演得：

φ(n)=∑d∣nμ(d)nd\varphi(n)=\sum_{d\mid n} \mu(d)\frac{n}{d}

统计互质对数

∑i=1n∑j=1n[gcd⁡(i,j)=1]=∑d=1nμ(d)⌊nd⌋2\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

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

再变为 ∑i=1⌊nk⌋∑j=1⌊mk⌋∑d∣gcd⁡(i,j)μ(d)\sum_{i=1}^{\lfloor \frac{n}{k} \rfloor} \sum_{j=1} ^{\lfloor \frac{m}{k} \rfloor} \sum _{d | \gcd(i,j)} \mu(d)。

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

∑dμ(d)∑i=1⌊nk⌋[d ∣ i]∑j=1⌊mk⌋[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]

最后化简：

∑dμ(d)⌊ndk⌋⌊mdk⌋\sum_d\mu(d)\lfloor\dfrac{n}{dk}\rfloor\lfloor\dfrac{m}{dk}\rfloor

但是数据太强了，直接计算过不了，所以我们可以用到积性函数的性质做前缀和用 O(n)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

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

按照 P2522 的套路变为：

∑k∈Prime∑dμ(d)⌊ndk⌋⌊mdk⌋\sum _{k \in \text{Prime}} \sum_d \mu(d) \lfloor \dfrac{n}{dk} \rfloor \lfloor \dfrac{m}{dk} \rfloor

发现过不了。

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

∑T=1min⁡(n,m)⌊nT⌋⌊mT⌋∑k∣T,k∈Primeμ(Tk)\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,mn,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))

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

userId_undefined
去预览
0/2000

全部评论 79

热门讨论