莫比乌斯反演学习笔记中，有哪些关键点需要重点掌握？

本文共计2322个文字，预计阅读时间需要10分钟。

莫比乌斯反演学习笔记：前置知识+(x|y)+(x)是(√y)的因数。(S)=(S)为真，(S=1)，若(S)为假，则(S=0)。（如(gcd(11,45)=14)为真）。(sum:)求和符号。(prod:)连乘符号。

莫比乌斯反演学习笔记 前置知识

• \(x|y:\) \(x\) 是 \(y\) 的因数。

  

• \([S]:\) 若 \(S\) 为真，\([S]=1\)，若 \(S\) 为假，则 \([S]=0\)（如 \([gcd(11,45)=14]=0\)）。

• \(\sum:\) 求和符号。

• \(\prod:\) 连乘符号。

• \(n=\prod\limits_{i=1}^{k}p_i^{q_i}:\) 将 \(n\) 分解质因数。即默认 \(p_i\) 两两不同且为质数。

基本定义

先介绍 \(\mu\) 函数：

• \(\mu(1)=1\)。

• 若 \(i\) 含有平方因子，\(\mu(i)=0\)。

• 若 \(i\) 为奇数个不同的质因数的乘积，\(\mu(i)=-1\)。