Matt Blog

狄利克雷卷积 Dirichlet

定义

其本质是一种运算，可以用 $*$ 表示。

$h(x)=f(x)*g(x)=\sum_{d|x}f(d)g(\frac{x}{d})=\sum_{ab=x}f(a)g(b)$

积性函数 $f(x)$ 满足 $\forall (a,b)=1,f(ab)=f(a)f(b)$。

完全积性函数 $f(x)$ 满足 $f(ab)=f(a)f(b)$。

可以使用线性筛算出积性函数。

性质

交换律：$f*g=g*f$。

结合律：$(f*g)*h=f*(g*h)$。

分配律：$(f+g)*h=f*h+g*h$。

若 $f$ 和 $g$ 是积性函数，则 $f*g$ 也是积性函数。

若 $f$ 是积性函数，则 $f$ 的逆元也是积性函数。

逆元

单位函数 $\varepsilon$，$f*\varepsilon =f$。

若 $g$ 满足 $f*g=\varepsilon$，则称 $g(x)$ 是 $f(x)$ 的逆元。逆元唯一。

ps：目前还不太懂这是什么，但好像可以理解为 $\varepsilon(n)=\begin{cases}1&n=1\\0&n\not=1\end{cases}$。

$g(x)= \dfrac{\varepsilon(x)-\sum_{d|x,d\not=1} f(d)f(\dfrac{x}{d})}{1}$

莫比乌斯函数 Möbius

定义式

$n=p_1^{a_1}p_2^{a_2}...p_k^{a_k}\\ \mu(n)=\begin{cases} 1 &n=1 \\ 0 & \exist i \le k,a_i>1 \\ (-1)^k& else \end{cases}$

性质

$\mu(x)$ 是积性函数。

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

即 $\sum_{d|n}\mu(d)=\varepsilon(n),\mu*1=\varepsilon$。在狄利克雷卷积中，莫比乌斯函数是常数函数 $1$ 的逆元。

证明

$n=p_1^{a_1}p_2^{a_2}...p_k^{a_k},n'=p_1p_2...p_k\\ \because \mu(k \times a^2)=0 \\ \therefore \sum_{d|n}\mu(d)=\sum_{d|n'}\mu(d)$

则现在就是尝试在 $k$ 个互异质数中选择一个集合，若集合大小为奇数，答案 -1，否则答案 +1。$k>1$ 时，$\sum_{d|n'}\mu(d)=\sum_{i=0}^k\binom{k}{i}\times(-1)^i$。二项式定理是 $(a+b)^n=\sum_{i=0}^n\binom{n}{i}a^ib^{n-i}$，将 $a=-1,b=1$ 带入则是 $(1+(-1))^n=\sum_{i=0}^n\binom{n}{i}\times(-1)^i=0$。故 $k>1$ 时，$\sum_{d|n}\mu(d)=0$。剩下情况不难自证。

ps：以上证明只是本人在初学时的结论，不保证正确，等待未来的我修改或确认。

反演结论

$[\gcd(i,j)=1]=\sum_{d|\gcd(i,j)}\mu(d)$

例题

「HAOI 2011」Problem b

求 $\displaystyle{\sum_{i=x}^n\sum_{j=y}^m[\gcd(i,j)=k]} ,(1 \le T,x,y,n,m,k \le 10^5)$。

$f(a,b,k)=\sum_{i=1}^a\sum_{j=1}^b[\gcd(i,j)=k] \tag{1}$

$\sum_{i=x}^n\sum_{j=y}^m[\gcd(i,j)=k]=f(n,m,k)-f(x-1,m,k)-f(n,y-1,k)+f(x-1,y-1,k) \tag{2}$

$f(a,b,k)=\sum_{i=1}^{\left \lfloor \frac{a}{k} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{b}{k} \right \rfloor}[\gcd(i,j)=1] \tag{3}$

$=\sum_{i=1}^{\left \lfloor \frac{a}{k} \right \rfloor}\sum_{j=1}^{\left \lfloor \frac{b}{k} \right \rfloor}\sum_{d|\gcd(i,j)}\mu(d) \tag{4}$

$=\sum_{d}\mu(d)\sum_{i=1}^{\left \lfloor \frac{a}{k} \right \rfloor}[d|i]\sum_{j=1}^{\left \lfloor \frac{b}{k} \right \rfloor}[d|j] \tag{5}$

$=\sum_{d=1}^{\min(\left \lfloor \frac{a}{k} \right \rfloor,\left \lfloor \frac{b}{k} \right \rfloor)}\mu(d)\left \lfloor \frac{\left \lfloor \frac{a}{k}\right \rfloor}d \right \rfloor\left \lfloor \frac{\left \lfloor \frac{b}{k}\right \rfloor}d \right \rfloor \tag{6}$

$(1)$ 到 $(2)$ 的过程是二维差分，$(3)$ 到 $(4)$ 的过程就是反演结论的使用，$(5)$ 到 $(6)$ 是因为 $\displaystyle\sum_{i=1}^{\left \lfloor \frac{a}{k} \right \rfloor}[d|i]$ 就是 $[1,\left \lfloor \frac{a}{k} \right \rfloor]$ 中是 $d$ 的倍数的个数，另一个同理。

使用 $O(V)$ 线性筛预处理出 $\mu(i)$ 和 $\sum_{i=1}^n\mu(i)$，使用整除分块在 $O(\sqrt V)$ 算出 $(6)$。总时间复杂度为 $O(V+\sum\sqrt V)$。

阶

定义

由欧拉定理可知，$(a,m)=1$，$a^{\varphi(m)} \equiv 1(\bmod m)$。故存在最小正整数满足 $a^n \equiv 1(\bmod m)$，称 $n$ 为 $a$ 模 $m$ 的阶，记作 $\operatorname{ord}_m(a)$。

性质

$a,a^2...a^{\operatorname{ord}_m(a)}$ 模 $m$ 两两不同余。

若 $a^p \equiv a^q(\bmod m)$，则 $p\equiv q(\bmod \operatorname{ord}_m(a))$。

$(a,m)=(b,m)=1 \\ \operatorname{ord}_m(ab)=\operatorname{ord}_m(a)\operatorname{ord}_m(b) \Leftrightarrow gcd(\operatorname{ord}_m(a),\operatorname{ord}_m(b))=1$

原根 primitive-root

定义

若 $(g,m)=1$，且 $\operatorname{ord}_m(g)=\varphi(m)$，则称 $g$ 为模 $m$ 的原根。

性质

对于 $m \ge 3,(g,m)=1$，则 $g$ 是模 $m$ 的原根 $\Leftrightarrow$ 对于 $\varphi(m)$ 的每个质因子 $p$，都有 $g^{\frac{\varphi(m)}{p}} \not\equiv 1(\bmod m)$。

若 $m$ 有原根，则原根个数为 $\varphi(\varphi(m))$。

原根存在定理：一个数 $m$ 存在原根当且仅当 $m=2,4,p^a,2p^a$，$p$ 为奇质数。

$a$ 的最小原根大约在 $\sqrt[4]a$，long long 内的都可以暴力枚举。

设 $g$ 为 $n$ 的最小原根，则 $n$ 的原根集合 $S=\{g^s|(s,\varphi(n))=1\}$。

部分证明

由第 1 条得，$\forall \text{p is prime and }p| \varphi(n),g^{\frac{\varphi(n)}{p}}\not=1(\bmod n)$。

$g^{s^{\frac{\varphi(n)}{p}}}=(g^{\varphi(n)})^\frac{s}{p}$，若 $\gcd(s,\varphi(n))>1$，则有一个 $p$ 使 $\frac{s}{p}$ 为正整数，由欧拉定理得 $g^{\varphi(n)}\equiv1(\bmod n)$，矛盾，故 $(s,\varphi(n))=1$，证明其必要性。

Burnside&Pólya 定理

$[X/G]=\dfrac{1}{|G|}\sum_{g\in G}|X^g| \tag{1}$

即本质不同的等价类个数是不动点个数的平均值。$|X^g|$ 表示 $X$ 在置换 $g$ 下的不动点个数。

$[X/G]=\dfrac1{|G|}\sum_{g\in G}m^{c(g)} \tag{2}$

$c(g)$ 表示置换 $g$ 形成了多少个环。

因为一个点在置换 $g$ 上成为不定点当且仅当这个点所在的环是同一种颜色，所以对每个环单独染色即可。

ps：$(1)$ 中的 $G$ 是定义在染色方案上的，即有 $n^m$ 种染色方案，$(2)$ 中的 $G$ 是定义在 $n$ 个点的轮换上，即有 $n$ 种旋转方式。