返回「邏輯與算法」主頁

本页面仅收录 Useful Formulas & Theorems in CP。对于知识点,另见 邏輯與算法:雜項 。
略去繁杂的证明和算法流程,多写柿子少废话。基本是看到什么有用的好吃的柿子就会塞进来。
文中可能出现中英文混用的情况,因为作者会优先使用更便于表达的语言(x。

恒等式

极值对偶恒等式

x+y=max⁡(x,y)+min⁡(x,y)∣x−y∣=max⁡(x,y)−min⁡(x,y)2max⁡(x,y)=(x+y)+∣x−y∣2min⁡(x,y)=(x+y)−∣x−y∣∣x−y∣=∣max⁡(x,y)−min⁡(x,y)∣x+y=(x∨y)+(x∧y)x⊕y=(x∨y)−(x∧y)2(x∨y)=(x+y)+(x⊕y)2(x∧y)=(x+y)−(x⊕y)x⊕y=(x∨y)⊕(x∧y)\begin{aligned} x + y & = \max(x, y) + \min(x, y) \\ |x-y| & = \max(x, y) - \min(x, y) \\ 2 \max(x, y) & = (x + y)+ |x-y| \\ 2 \min(x, y) & = (x + y) - |x-y| \\ \lvert x - y \rvert & = \lvert \max(x, y) - \min(x, y) \rvert \\ \\ x+y & = (x \vee y) + (x \wedge y) \\ x \oplus y & = (x \vee y) - (x \wedge y) \\ 2 (x \vee y) & = (x + y) + (x \oplus y) \\ 2 (x \wedge y) & = (x + y) - (x \oplus y) \\ x \oplus y & = (x \lor y) \oplus (x \land y) \end{aligned}

Combinatorial Counting

组合数

定义

  • (nr)=n(n−1)⋯(n−r+1)r(r−1)⋯1=n!r!(n−r)!\displaystyle \binom{n}{r} = \frac{n (n - 1) \cdots (n - r + 1)}{r (r - 1) \cdots 1} = \frac{n!}{r! (n - r)!}
  • (−nr)=(−n)(−n−1)⋯(−n−r+1)r!=(−1)r(n+r−1r)\displaystyle \binom{-n}{r} = \dfrac{(-n) (-n - 1) \cdots (-n - r + 1)}{r!} = (-1)^{r} \binom{n + r - 1}{r} (Upper Negation)
  • (nn1 n2 … nk)=(nn1)(n−n1n2)⋯(n−n1−⋯−nk−1nk)=n!n1! n2! … nk!,\dbinom{n}{n_{1}\ n_2\ \dots\ n_k}=\dbinom{n}{n_{1} }\dbinom{n-n_{1} }{n_2}\cdots \dbinom{n-n_{1}-\dots -n_{k-1} }{n_k}=\dfrac{n!}{n_{1}!\ n_2!\ \dots\ n_k!},

递推定义

  • (nr)=n−r+1r(nr−1)=nr(n−1r−1)\displaystyle \binom{n}{r} = \frac{n - r + 1}{r} \binom{n}{r - 1} = \frac{n}{r} \binom{n - 1}{r - 1}
  • (nr)=(n−1r−1)+(n−1r)\displaystyle \binom{n}{r} = \binom{n - 1}{r - 1} + \binom{n - 1}{r}

常用求和式

  • ∑ℓ=0N(ℓM)=(N+1M+1)\displaystyle \sum_{\ell = 0}^{N} \binom{\ell}{M} = \binom{N + 1}{M + 1} (Hockey-stick Identity)
  • ∑k=0n(nk)=2n\displaystyle \sum_{k = 0}^{n} \binom{n}{k} = 2^{n}
  • ∑k=0n(−1)k(nk)={1,n=00,n>0\displaystyle \sum_{k = 0}^{n} (-1)^{k} \binom{n}{k} = \begin{cases} 1, & n = 0 \\ 0, & n > 0 \end{cases}
  • ∑k=0nk(nk)=n⋅2n−1\displaystyle \sum_{k = 0}^{n} k \binom{n}{k} = n \cdot 2^{n - 1}
  • ∑k=0⌊n/2⌋(n−kk)=Fibonacci(N+1)\displaystyle \sum_{k = 0}^{\lfloor n / 2 \rfloor} \binom{n - k}{k} = \text{Fibonacci}(N + 1)
  • (nk)(km)=(nm)(n−mk−m)\displaystyle \binom{n}{k} \binom{k}{m} = \binom{n}{m} \binom{n - m}{k - m}
  • ∑k=mn(nk)(km)=(nm)2n−m\displaystyle \sum_{k = m}^{n} \binom{n}{k} \binom{k}{m} = \binom{n}{m} 2^{n - m}
  • ∑m=0n∑k=mn(nk)(km)=3n\displaystyle \sum_{m = 0}^{n} \sum_{k = m}^{n} \binom{n}{k} \binom{k}{m} = 3^{n}

Binomial Theorem

  • (1+x)n=∑k=0n(nk)xk\displaystyle (1+x)^{n} = \sum_{k=0}^{n} \binom{n}{k} x^{k}
  • (1−x)−n=∑k=0∞(−nk)(−x)k=∑k=0∞(n+k−1k)xk\displaystyle (1-x)^{-n} = \sum_{k=0}^{\infty} \binom{-n}{k} (-x)^{k} = \sum_{k=0}^{\infty} \binom{n + k - 1}{k} x^{k}
  • (x1+x2+⋯+xm)n=∑k1+k2+⋯+km=n(nk1,k2,…,km)x1k1x2k2…xmkm\displaystyle (x_{1}+x_2+\dots +x_m)^n = \sum_{k_1 + k_2 + \dots + k_m = n} \binom{n}{k_{1}, k_2, \dots, k_m} x_{1}^{k_{1} } x_2^{k_2} \dots x_m^{k_m}

Vandermonde’s Convolution

∑r=0R(Nr)(MR−r)=(N+MR)⇕∑r=0R(−Nr)(−MR−r)=(−N−MR)⇕∑r=0R(N+r−1r)(M+R−r−1R−r)=(N+M+R−1R)\begin{aligned} \sum_{r=0}^{R} \binom{N}{r} \binom{M}{R-r} &= \binom{N+M}{R} \\ &\Updownarrow \\ \sum_{r=0}^{R} \binom{-N}{r} \binom{-M}{R-r} &= \binom{-N-M}{R} \\ &\Updownarrow \\ \sum_{r=0}^{R} \binom{N+r-1}{r} \binom{M+R-r-1}{R-r} &= \binom{N+M+R-1}{R} \end{aligned}

求组合数

 mod \bmodNN时空
杨辉三角二维递推任意较小O(N2+Q)O(N^2 + Q)
预处理阶乘素数较大且不超过素数O(N+log⁡p+Q)O(N+\log p + Q)
普通 Lucas:较小的素数无限制O(p+Qlog⁡n)O(p + Q \log n)
预处理非素数阶乘 + Legendre 修正素数幂较大O(N+log⁡p+Qlog⁡n)O(N+\log p + Q \log n)
扩展 Lucas较小的素数幂无限制O(pα+Qlog⁡n+Qlog⁡p)O(p^{\alpha} + Q \log n + Q \log p)

利用 CRT 将素数幂合并,实现任意模数。

球盒模型的四种可能形式

已知将 ii 个有 / 无标号的小球放入一个盒子里有 aia_{i} 种方案,问将 nn 个小球放入 kk 个有 / 无标号的允许为空的盒子,有多少种方案。

设 A(z)A(z) 代表单个盒子装小球的方案,具体地,如果小球无标号,使用 OGF A(z)=∑n=0∞anzn\displaystyle A(z) = \sum_{n=0}^{\infty} a_{n} z^{n};如果小球有标号,使用 EGF A(z)=∑n=0∞ann!zn\displaystyle A(z) = \sum_{n=0}^{\infty} \dfrac{a_{n} }{n!}z^{n}。

根据小球和盒子是否有标号(即是否可区分),分为四种可能形式。

有标号球有标号盒——乘法原理

已知将 ii 个有标号的小球放入一个盒子里有 aia_{i} 种方案,那么将 nn 个小球放入 kk 个有标号的允许为空的盒子的方案数为

n![zn](∑n=0∞ann!zn)kn! [z^{n}] \Bigg(\sum_{n=0}^{\infty} \dfrac{a_{n} }{n!}z^{n} \Bigg)^{k}

特别地,若 ai=1a_{i} = 1,方案数是我们熟知的乘法原理 knk^n。

无标号球有标号盒——插板法

已知将 ii 个无标号的小球放入一个盒子里有 aia_{i} 种方案,那么将 nn 个小球放入 kk 个有标号的允许为空的盒子的方案数为

[zn](∑n=0∞znan)k[z^{n}] \Bigg(\sum_{n=0}^{\infty} z^{n} a_{n} \Bigg)^{k}

特别地,若 ai=1a_{i} = 1,问题化为 x1+x2+⋯+xk=nx_1+x_2+\cdots+x_k=n 的非负整数解组数

=[zn]1(1−z)k=(n+k−1k−1)= [z^{n}] \frac{1}{(1-z)^{k} } = \binom{n + k - 1}{k - 1}

如果盒子不允许为空,方案数为

[zn](∑n=1∞znan)k[z^{n}] \Bigg(\sum_{n=1}^{\infty} z^{n} a_{n} \Bigg)^{k}

特别地,若 ai=1a_{i} = 1,问题化为 x1+x2+⋯+xk=nx_1+x_2+\cdots+x_k=n 的正整数解组数

=[zn]zk(1−z)k=[zn−k]1(1−z)k=(n−1k−1)= [z^{n}] \frac{z^{k} }{(1-z)^{k} } = [z^{n - k}] \frac{1}{(1-z)^{k} } = \binom{n - 1}{k - 1}

无标号球无标号盒——背包问题 / 整数分拆

给定 NN 种物品,体积分别为 ViV_i,都有无限件。给定 MM,对于 m∈[1,M]m\in [1,M],求用这些物品恰好装 mm 体积的方案数  mod 998244353\bmod 998244353。N⩽105,Vi⩽M⩽105N \leqslant 10^5,V_{i} \leqslant M \leqslant 10^5。

设 aia_{i} 表示体积为 ii 的物品种类数。一个体积为 ViV_{i} 的物品可以看作一个能且仅能装 ViV_{i} 个无标号小球的盒子。问题化为,已知将 ii 个无标号的小球放入一个盒子里有 aia_{i} 种方案,问将 nn 个小球放入任意个无标号的盒子,有多少种方案。

设商品类型构成集合 A\mathcal{A},其 OGF

A(z)=∑i=1NzVi=∑k=1∞zkakA(z) = \sum_{i=1}^{N} z^{V_{i} } = \sum_{k=1}^{\infty} z^{k} a_{k}

问题要求对集合 A\mathcal{A} 中的对象进行无标号的多重集构造 (Multiset Construction, MSET),其 OGF

B(z)=exp⁡∑n=1∞A(zn)nB(z) = \exp \sum_{n=1}^{\infty} \frac{A(z^{n})}{n}

答案便是 [zm]B(z)[z^{m}]B(z),计算复杂度 O(Mlog⁡M)\mathcal{O}(M\log M)。

如果不了解 MSET 的公式,也可按如下过程推导,

∏k=1M(∑n=0∞znk)fk=∏k=1M1(1−zk)fk=exp⁡∑k=1Mfklog⁡11−zk=exp⁡∑k=1Mfk∑n=1∞znkn=exp⁡∑n=1∞F(zn)n\prod_{k=1}^{M} \Bigg(\sum_{n=0}^{\infty} z^{n k} \Bigg)^{f_{k} } = \prod_{k=1}^{M} \frac{1}{(1 - z^{k})^{f_{k} } } = \exp \sum_{k=1}^{M} f_{k} \log \frac{1}{1 - z^{k} } = \exp \sum_{k=1}^{M} f_{k} \sum_{n=1}^{\infty} \frac{z^{n k} }{n} = \exp \sum_{n=1}^{\infty} \frac{F(z^{n})}{n}

特别地,若 ai=1a_{i} = 1,这就是整数分拆问题。将正整数 nn 分拆成若干正整数之和的方案数为

p(n)=[zn]exp⁡∑n=1∞znn(1−zn)p(n) = [z^{n}] \exp \sum_{n=1}^{\infty} \frac{z^{n} }{n (1 - z^{n})}

设 p(n,k)p(n, k) 表示将正整数 nn 分拆成正好 kk 个正整数之和的方案数,则将正整数 nn 分拆成正好 kk 个非负整数之和的方案数为 p(n+k,k)p(n + k, k)。

这 p(n,k)p(n, k) 无显式计算公式,但有递归方程

p(n,k)=p(n−1,k−1)+p(n−k,k)p(n, k) = p(n - 1, k - 1) + p(n - k, k)

递归终点 p(0,0)=1, p(n,0)=0p(0, 0) = 1, \ p(n, 0) = 0。

p(n,k)=[zn]zk∑n=1k11−znp(n, k) = [z^{n}] z^{k} \sum_{n=1}^{k} \frac{1}{1 - z^{n} }

有标号球无标号盒——Second Stirling Numbers

已知将 ii 个有标号的小球放入一个盒子里有 aia_{i} 种方案,那么将 nn 个小球放入 kk 个无标号的不允许为空的盒子(即非空子集)的方案数为

n![zn]1k!(∑n=1∞ann!zn)kn! [z^{n}] \dfrac{1}{k!} \Bigg(\sum_{n=1}^{\infty} \dfrac{a_{n} }{n!}z^{n} \Bigg)^{k}

特别地,若 ai=1a_{i} = 1,

n![zn]1k!(ez−1)kn! [z^{n}] \dfrac{1}{k!} (\mathrm e^{z} - 1 )^{k}

这就是第二类斯特林数 S(n,k)S(n, k),其递归方程

S(n,k)=S(n−1,k−1)+k⋅S(n−1,k)S(n, k) = S(n - 1, k - 1) + k\cdot S(n - 1, k)

如果不限制 kk 的大小,即把 nn 个球分到任意多个无标号的不允许为空的盒子(即非空子集)中,方案数有非常简洁的形式

n![zn]∑k=0∞1k!(ez−1)k=n![zn]exp⁡(ez−1)n! [z^{n}] \sum_{k=0}^{\infty} \dfrac{1}{k!} (\mathrm e^{z} - 1 )^{k} = n! [z^{n}] \exp(\mathrm e^{z} - 1)

这就是贝尔数 Bn=∑k=0nS(n,k)\displaystyle B_{n} = \sum_{k=0}^{n}S(n, k)。

设基本组合结构 A\mathcal{A} 的 EGF A(z)A(z),那么由这些基本结构 A\mathcal{A} 组成的集合 B\mathcal{B} 的 EGF B(z)B(z) 满足

B(z)=exp⁡A(z)B(z) = \exp A(z)

第一类无符号斯特林数 su(n,k)s_{u}(n, k) 表示将一个长为 nn 置换划分为 kk 个轮换的方法数,递归方程

su(n,k)=su(n−1,k−1)+(n−1)⋅su(n−1,k)s_{u}(n, k) = s_{u}(n - 1, k - 1) + (n - 1) \cdot s_{u}(n - 1, k)

OGF

xn↑=∑k=0nsu(n,k)xkx^{n \uparrow} = \sum_{k=0}^{n} s_{u}(n, k) x^{k}

第一类有符号斯特林数 ss(n,k)=(−1)n−ksu(n,k)s_{s}(n, k) = (-1)^{n-k} s_{u}(n, k) 的 OGF

xn↓=∑k=0nss(n,k)xkx^{n \downarrow} = \sum_{k=0}^{n} s_{s}(n, k) x^{k}

对于一个排列 pp,我们总是能构造出另一个排列 qq,使得 pp 的置换环最大元素的集合,恰好等于 qq 的前缀最大值的集合。反过来,对于一个排列 pp,我们也总能构造出另一个排列 qq,使得 pp 的前缀最大值的集合,恰好等于 qq 的置换环最大元素的集合。

给定 N,KN,K 和集合 T=(T1,T2,…,TK)T = (T_{1}, T_{2}, \dots, T_{K}),满足集合 SS 内的元素恰为排列 q∈SNq \in S_{N} 的前缀最大值的排列 q∈SNq \in S_{N} 的个数为

∏j=1,j∉TK(N−j)\prod_{j = 1, j \notin T}^{K} (N - j)

若 TK≠NT_{K} \neq N,上式自然为 0。

给定 N,KN,K 和集合 T=(T1=1,T2,…,TK)T = (T_{1} = 1, T_{2}, \dots, T_{K}),满足排列 qq 的前缀最大值的下标恰好构成集合 SS 的排列 q∈SNq \in S_{N} 的个数为

(N−1)!∏j=2K(Tj−1)\dfrac{(N - 1)!}{\prod_{j=2}^{K}(T_{j} - 1)}

Number Theory

Lifting The Exponent Lemma (LTE)

Let p≠2p \neq 2,

p∣x−y, p∤x  ⟹  νp(xn−yn)=νp(x−y)+νp(n)2∤n, p∣x+y, p∤x  ⟹  νp(xn+yn)=νp(x+y)+νp(n)\begin{aligned} p \mid x - y, \ p \nmid x & \implies \nu_p(x^n-y^n)=\nu_p(x-y) + \nu_{p}(n) \\ 2 \nmid n, \ p \mid x + y, \ p \nmid x & \implies \nu_p(x^n+y^n)=\nu_p(x+y) + \nu_{p}(n) \end{aligned}

Let p=2p = 2,

2∤n, 2∤x, 2∤y  ⟹  ν2(xn−yn)=ν2(x−y)2∣n, 2∤x, 2∤y  ⟹  ν2(xn−yn)=ν2(x−y)+ν2(x+y)+ν2(n)−12∤n, 2∤x, 2∤y  ⟹  νp(xn+yn)=νp(x+y)+νp(n)\begin{aligned} 2 \nmid n, \ 2 \nmid x, \ 2 \nmid y & \implies \nu_2(x^n-y^n)=\nu_2(x-y) \\ 2 \mid n, \ 2 \nmid x, \ 2 \nmid y & \implies \nu_2(x^n-y^n)=\nu_2(x-y)+\nu_2(x+y)+\nu_2(n)-1 \\ 2 \nmid n, \ 2 \nmid x, \ 2 \nmid y & \implies \nu_p(x^n+y^n)=\nu_p(x+y) + \nu_{p}(n) \end{aligned}

Proof. 设 n=2kmn=2^k m,其中 k=ν2(n)≥1k = \nu_2(n)\ge1,mm 为奇数。
令 A=x2k,B=y2kA=x^{2^k},B=y^{2^k},由 Am−Bm=(A−B)(Am−1+Am−2B+⋯+Bm−1)A^m-B^m=(A-B)(A^{m-1}+A^{m-2}B+\cdots+B^{m-1}),括号内是 mm 个奇数之和,故为奇数。因此 ν2(xn−yn)=ν2(x2k−y2k)\nu_2(x^n-y^n)=\nu_2(x^{2^k}-y^{2^k})。
用平方差公式 x2k−y2k=(x−y)(x+y)∏j=1k−1(x2j+y2j)x^{2^k}-y^{2^k}=(x-y)(x+y)\prod_{j=1}^{k-1}(x^{2^j}+y^{2^j}) 展开,ν2(x2k−y2k)=ν2(x−y)+ν2(x+y)+∑j=1k−1ν2(x2j+y2j)\nu_2(x^{2^k}-y^{2^k})=\nu_2(x-y) + \nu_2(x+y) + \sum_{j=1}^{k-1}\nu_2(x^{2^j}+y^{2^j})。
考虑到奇数的平方模 88 余 11,所以对每个 j≥1j\ge1,都有 x2j+y2j≡1+1=2(mod8)x^{2^j}+y^{2^j}\equiv 1+1=2\pmod8,即 ν2(x2j+y2j)=1\nu_2 (x^{2^j}+y^{2^j})=1,代回原式即证。

Ex 求 M=∑i=1nv5(i!)\displaystyle M=\sum_{i=1}^{n}v_5(i!)。([VJwin6H - 阶乘之乘](https: //www.luogu.com.cn/problem/P2388))

M=∑i=1nv5(i!)=∑i=1n∑k=15k≤i⌊i5k⌋=∑k=15k≤n∑i=1n⌊i5k⌋=∑k=15k≤n[5k+2⋅5k+⋯+(⌊n5k⌋−1)⋅5k+⌊n5k⌋(n mod 5k+1)]=∑k=15k≤n[5k2⌊n5k⌋(⌊n5k⌋−1)+⌊n5k⌋(n mod 5k+1)]=∑5≤i=5k≤n[i2⌊ni⌋(⌊ni⌋−1)+⌊ni⌋(n mod i+1)]\begin{align} M &= \sum_{i=1}^{n}v_5(i!) = \sum_{i=1}^{n}\sum_{k=1}^{5^k\le i}\bigg\lfloor\dfrac{i}{5^k}\bigg\rfloor = \sum_{k=1}^{5^k\le n}\sum_{i=1}^{n}\bigg\lfloor\dfrac{i}{5^k}\bigg\rfloor \\ &= \sum_{k=1}^{5^k\le n}\bigg[ 5^k +2\cdot5^k +\dots +\bigg(\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor-1\bigg)\cdot5^k +\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor\Big(n\bmod{5^k}+1\Big) \bigg] \\ &= \sum_{k=1}^{5^k\le n}\bigg[\frac{5^k}{2}\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor\bigg(\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor-1\bigg) +\bigg\lfloor\dfrac{n}{5^k}\bigg\rfloor\Big(n\bmod{5^k}+1\Big) \bigg] \\ &= \sum_{5\le i=5^k\le n}^{}\bigg[\frac{i}{2}\bigg\lfloor\dfrac{n}{i}\bigg\rfloor\bigg(\bigg\lfloor\dfrac{n}{i}\bigg\rfloor-1\bigg) +\bigg\lfloor\dfrac{n}{i}\bigg\rfloor\Big(n\bmod{i}+1\Big) \bigg] \\ \end{align}

Arithmetic Functions

通俗地讲,input 是 integer 的 function,即 Arithmetic Function。

Completely Multiplicative

  • For all x,yx, y, f(xy)=f(x)f(y)f(x y) = f(x) f(y).
  • f(n)=∏p∣n[f(p)]νp(n)\displaystyle f(n) = \prod_{p \mid n} [f(p)]^{\nu_{p}(n)}.
  • If ff and gg are completely multiplicative, then so are f(nk)f(n^{k}), [f(n)]k[f(n)]^{k}, (f⋅g)(n)=f(n)g(n)(f \cdot g)(n) = f(n)g(n), (f∗g)(n)(f \ast g)(n).

Examples:

  1. Unit Function I(n)=[n=1]I(n) = [n = 1]
    • Identity for Dirichlet convolution, 类比单位矩阵
  2. Power Function id⁡k(n)=nk\operatorname{id}_{k}(n) = n^{k}
    • Constant Function id⁡0(n)=1(n)=1\operatorname{id}_{0}(n) = 1(n) = 1
    • Identity Function id⁡1(n)=n\operatorname{id}_{1}(n) = n

Multiplicative

  • For all x⊥yx \perp y, f(xy)=f(x)f(y)f(x y) = f(x) f(y).
  • f(n)=∏p∣nf(pνp(n))\displaystyle f(n) = \prod_{p \mid n} f(p^{\nu_{p}(n)}).
  • f(pνp(n))≠[f(p)]νp(n)\displaystyle f(p^{\nu_{p}(n)}) \neq [f(p)]^{\nu_{p}(n)}.
  • If ff and gg are multiplicative, then so are f(nk)f(n^{k}), fk(n)f^{k}(n), (f⋅g)(n)=f(n)g(n)(f \cdot g)(n) = f(n)g(n), (f∗g)(n)(f \ast g)(n).

Examples:

  1. Divisor Function σk(n)=∑d∣ndk\displaystyle \sigma_{k}(n) = \sum_{d \mid n} d^{k}
    • 约数个数 (Number of Divisors): τ(n)=σ0(n)=∑d∣n1=∏p∣n(νp(n)+1)\displaystyle \tau(n) = \sigma_0(n) = \sum_{d \mid n} 1 = \prod_{p \mid n} \big(\nu_{p}(n) + 1\big)
    • 约数和 (Sum of Divisors): σ(n)=σ1(n)=∑d∣nd=∏p∣npνp(n)+1−1p−1\displaystyle \sigma(n) = \sigma_1(n) = \sum_{d \mid n} d = \prod_{p \mid n} \frac{p^{\nu_{p}(n)+1} - 1}{p - 1}
  2. Möbius Function μ(n)={1,n=10,∃d>1,d2∣n(−1)ω(n),otherwise\mu(n) = \begin{cases} 1, & n = 1 \\ 0, & \exists d > 1, d^{2} \mid n \\ (-1)^{\omega(n)}, & \text{otherwise} \end{cases}
    • μ=1−1  ⟺  μ∗1=I  ⟺  ∑d∣nμ(d)=[n=1]=I(n)\mu = 1^{-1} \iff \mu * 1 = I \iff \displaystyle \sum_{d \mid n} \mu(d) = [n = 1] = I(n)
    • ∑d∣n,d∣mμ(d)=[n⊥m]\displaystyle \sum_{d \mid n, d \mid m} \mu(d) = [n \perp m]
    • Ex. S=∑n=1M∑m=1M[n⊥m]=∑n=1M∑m=1M∑d∣gcd⁡(n,m)μ(d)=∑n=1M∑m=1M∑d=1M[d∣n][d∣m]μ(d)=∑d=1Mμ(d)∑n=1M[d∣n]∑m=1M[d∣m]=∑d=1Mμ(d)⌊Md⌋⌊Md⌋\displaystyle S = \sum_{n=1}^{M}\sum_{m=1}^{M}[n \perp m] = \sum_{n=1}^{M}\sum_{m=1}^{M}\sum_{d\mid\gcd(n, m)}\mu(d) = \sum_{n=1}^{M}\sum_{m=1}^{M}\sum_{d=1}^{M}[d \mid n][d \mid m]\mu(d) = \sum_{d=1}^{M}\mu(d)\sum_{n=1}^{M}[d \mid n]\sum_{m=1}^{M}[d \mid m] = \sum_{d=1}^{M}\mu(d)\Big\lfloor\frac{M}{d}\Big\rfloor\Big\lfloor\frac{M}{d}\Big\rfloor
  3. Euler’s Totient Function φ(n)=∑i=1n[i⊥n]=n∏p∣n(1−1p)\displaystyle \varphi(n) = \sum_{i=1}^n [i \perp n] = n \prod_{p \mid n} \left(1 - \frac{1}{p}\right) — 1∼n1\sim n 中与 nn 互素的数量
    • ∑i=1ni [i⊥n]=nφ(n)2(n>1)\displaystyle \sum_{i=1}^{n} i \ [i \perp n] = \frac{n\varphi(n)}{2} \quad (n > 1) — 1∼n1\sim n 中与 nn 互素的数之和
    • φ=id∗μ  ⟺  φ∗1=id  ⟺  ∑d∣nφ(d)=n\displaystyle \varphi = \text{id} \ast \mu \iff \varphi \ast 1 = \text{id} \iff \sum_{d \mid n} \varphi(d) = n
    • ∑d∣n,d∣mφ(d)=(n,m)\displaystyle\sum_{d \mid n, d \mid m} \varphi(d) = (n, m)
    • Ex. S=∑n=1Ngcd⁡(n,N)=∑n=1N∑d∣gcd⁡(n,N)ϕ(d)=∑d=1N∑n=1N[d∣n][d∣N]ϕ(d)=∑d=1N⌊Nd⌋[d∣N]ϕ(d)=∑d∣N⌊Nd⌋ϕ(d)\displaystyle S = \sum_{n=1}^{N} \gcd(n,N) = \sum_{n=1}^{N} \sum_{d\mid \gcd(n, N)} \phi(d) = \sum_{d=1}^{N} \sum_{n=1}^{N} [d\mid n][d\mid N]\phi(d) = \sum_{d=1}^{N} \left\lfloor \frac{N}{d} \right\rfloor [d\mid N]\phi(d) = \sum_{d\mid N} \left\lfloor \frac{N}{d} \right\rfloor \phi(d)

Additive

  • For all x⊥yx \perp y, f(xy)=f(x)+f(y)f(x y) = f(x) + f(y).
  • Example: 不同素因子个数 ω(n)\omega(n),在 n≤109n \le 10^{9} 的范围内,ω(n)\omega(n) 的最大值为 9

Completely Additive

  • For all x,yx, y, f(xy)=f(x)+f(y)f(x y) = f(x) + f(y).
  • Example: 所有素因子个数 (计重) Ω(n)\Omega(n)

Theorems

Prime Number

  1. Prime Number Theorem. lim⁡n→∞π(n)n/ln⁡(n)=1\displaystyle \lim_{n \to \infty} \dfrac{\pi(n)}{n/\ln(n)} = 1
  2. Density of Square-free Integers. The number of square-free integers Q(n)Q(n) up to nn satisfies: lim⁡n→∞Q(n)n=6π2=1ζ(2)\displaystyle \lim_{n \to \infty} \dfrac{Q(n)}{n} = \frac{6}{\pi^{2}} = \frac{1}{\zeta(2)}
  3. Chebyshev’s Theorem. For every integer n>1n > 1, there exists at least one prime pp such that n<p<2nn < p < 2n. (2025 Shenyang C)
  4. Twin Prime Conjecture. There are infinitely many pairs of primes (p,p+2)(p, p+2).
  5. Dirichlet’s Theorem on Arithmetic Progressions. For any two coprime positive integers aa and dd, the arithmetic progression a,a+d,a+2d,a+3d,…a, a+d, a+2d, a+3d, \dots contains infinitely many prime numbers.
  6. Green-Tao Theorem. The set of prime numbers contains arbitrarily long arithmetic progressions a,a+d,a+2d,a+3d,…a, a+d, a+2d, a+3d, \dots