#创作计划#莫比乌斯反演
2026-03-24 17:58:52
发布于：北京
头图
补充说明左边是一个同班的（五年级）同学 @你好。
正文
本人来随便学点高级数论 （其实是乱翻《算法竞赛》），有错轻喷。
莫比乌斯函数
即：
- 只要有 ，就有 。
- 若 （ 都是质数且所有数互不相同），则 。
计算
因为莫比乌斯函数是积性函数（即 且在 的情况下有 ），所以可以用在 时间内预处理出所有 内的莫比乌斯函数值。
[1] 质数的 为 。
[2] 如果一个数存在某个质因子的指数大于 ，那么它的 值为 。
- 值得注意的是，只有当数存在最小质因子的指数大于 时，才会被直接筛为
- 其他情况则由公式 完成，其中 是当前数， 是某个小于 的数
这种方法利用了积性函数的性质，使得每个数只被处理一次，从而实现线性筛。
示例 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
基础恒等式
这个式子是可以证明的，只是没那么简洁，这里不贴了，想看可以点我。
莫比乌斯反演
根据上方恒等式，可推出若两个函数满足：
则有：
莫比乌斯反演例子
欧拉函数
已知：
反演得：
统计互质对数
莫比乌斯反演例题
P2522
题目求的是 ，简单的类似二维前缀和的方法优化式子，然后消掉 变为 。
再变为 。
接下来交换求和顺序，在上述式子中，如果 要被枚举到，显然需要当且仅当 并且 。所以把这个部分计入到贡献当中：
最后化简：
但是数据太强了，直接计算过不了，所以我们可以用到积性函数的性质做前缀和用 的复杂度求解。
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
题目求的是 。
按照 P2522 的套路变为：
发现过不了。
观察到复杂度高的原因是双求和导致的，并且 重复出现了，所以可以令 。接下来，先枚举 ，显然 。先把后面的那个部分写下来。再考虑会有多少的 会加在这个部分上。我们要让求的和的值等价不变，由于 ，所以：
发现后面那个部分跟 没有一点关系了。所以这个求和被我们优化掉了。开个数组记录一下就可以了。
注意，交换求和的意义是将东西一起计算，我们通常都会把一些相同的东西给组合到一起，这样就可以离线处理一些东西，继而达到降低时间复杂度的意义。
我的这份 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))
应该不会有人第一遍就发现代码里的小彩蛋。
全部评论 214
我—是—小—学—生
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
求罐头
谢谢。
别忘了关注
2026-02-09 来自 浙江
49dddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddddd
2026-02-27 来自 浙江
1fdhgfdhfdhhghsssssttthhhhhhhhhhhhhssssssssssssssssssssssrrrrrrrrrrrrrttttttttttttttttttthhhhhhhhhhhhhhhhhhhhxcccrrrhsrrrrr
2026-02-27 来自 浙江
1
有帮助，赞一个