数论学习笔记
前言
数论，一个非常巨大的知识体系，总是会不时出现吓人。
这个工程只在每天中午花上大约半小时的时间进行学习，因此可能需要两个月的时间来完成一些比较基础的东西。
本 blog 参考 command_block 的 blog。
数论函数
Part 1：数论函数
约定：
-
\(\gcd(a,b)\) 简写为 \((a,b)\)；
-
\([p]\) ：若 \(p\) 为真，则值为 \(1\)；否则为 \(0\)。
-
若无特殊说明，我们一切出现的数字均为整数。
先上两个概念：
-
数论函数是值域为整数的函数。
-
两个数论函数的狄利克雷卷积是一个新的数论函数。
对于两个数论函数 \(f,g\) 它们的狄利克雷卷积记做 \(f*g\)。
狄利克雷卷积的计算方式如下：
显然，狄利克雷卷积满足交换率和结合律。
常见的数论函数有：
-
\(I(n)\)：恒等函数，值恒等于 \(1\)；
-
\(e(n)\)：元函数，值为 \(\left[n=1\right]\)（当且仅当 \(n=1\) 时值为 \(1\)），因此有 \(f*e=f\)；
-
\(id(n)\)：单位函数，值为 \(n\)。
-
\(\varphi(n)\)：欧拉函数，值为小于等于 \(n\) 的数中，与 \(n\) 互质的数的个数。
-
\(\mu(n)\)：莫比乌斯函数，值的计算比较复杂，暂且按下不表。
然后是两个新概念：
-
若 \(\forall_{a,b \in Z},f(a)f(b)=f(ab)\)，则 \(f\) 是完全积性函数；
-
若 \(\forall_{a,b \in Z,(a,b)=1},f(a)f(b)=f(ab)\)，则 \(f\) 是积性函数；
显然，若 \(f\) 是完全积性函数，则 \(f\) 一定是积性函数。
接下来我们来看积性函数的一些性质：
- 对于一个积性函数 \(f\)，有 \(f(1)=1\)。
证明：因为 \(f(1)=f(1)f(1)\)，所以 \(f(1)=1\)。
- 对于一个积性函数 \(f\) 和一个整数 \(n\)，对 \(n\) 进行质因数分解后得到 \(n =\prod p_i^{k_i}\)，有 \(f(n)=\prod f(p_i^{k_i})\)。
证明：显然，任意两个互异质数都互质，所以由定义可以简单得到。
- 两个积性函数的卷积还是积性函数。
证明：我们设 \(f_1,f_2\) 是两个积性函数，并且有 \(f_1*f_2=g\)。
那么对于 \(n,m\) 满足 \((n,m)=1\)，有：
如果你没有看懂，这里提供一些解释（第 \(i\) 步指推到第 \(i\) 行的过程）：
-
第二步的依据是乘法分配率；
-
第三步的依据是：因为 \((n,m)=1\)，所以 \(n\) 和 \(m\) 的因数集合的交必定为空集，所以每一个 \(ab\) 都唯一对应一个 \(a\) 和 \(b\)，故没有算重算漏。
-
对于积性函数 \(f\)，如果存在 \(e = f*g\)，那么我们称 \(g\) 是 \(f\) 在狄利克雷卷积意义下的逆，且 \(g\) 一定是一个积性函数。
证明：
我们要证明：\(\forall_{(a,b)=1} g(a)g(b)=g(ab)\)。
因为 \(e(n) = \sum \limits_{d \mid n} f(d)*g(n/d)\)。
当 \(a=1\) 或 \(b=1\) 时：
因为 \(e(1)=f(1)g(1) =1\)，且 \(f(1)=1\)，所以 \(g(1)=1\)，因此当 \(a=1\) 或 \(b=1\) 时，等式显然成立。
当 \(ab>1\) 时：
考虑数学归纳法。
假设我们已经证明 \(\forall_{a_0 < a,b_0 <b},g(a_0)g(b_0)=g(a_0b_0)\)，那么有：
转化的依据大部分是 \(f\) 和 \(g\) 是积性函数和乘法结合率。
- 若 \(e=f*g\)，则 \(f\) 和 \(g\) 互为在狄利克雷卷积意义下的逆。
特别地，我们记 \(f^{-1}\) 为 \(f\) 在狄利克雷卷积意义下的逆。
同时你也应该意识到：如果 \(f\) 是积性函数，那么 \(f^{-1}\) 也是积性函数。
Part 2：莫比乌斯反演
先来认识莫比乌斯函数。
先给出定义： \(\mu=I^{-1}\)。
那么莫比乌斯函数的作用是什么呢？
如果存在 \(g(n)=\sum \limits_{d \mid n} f(d)\)，那么有 \(g(n)=\sum \limits_{d \mid n} (1 \times f(d))\)，也就是 \(g=I*f\)，移项后有 \(f=I^{-1}*g\)。
如果存在 \(f\) 不好求，但是 \(g\) 好求的情况，这时候 \(\mu\) 就派上用场了。
接下来我们来研究 \(\mu\) 的值。
有一个套路是：研究一个积性函数时，可以从它在一个质数的若干次幂处的取值。
所以对于 \(\mu(p^k)\)。
-
当 \(k=0\) 时，有 \(\mu(1)=1\)。
-
当 \(k=1\) 时：
因为 \(\mu = I^{-1}\)，所以有 \(e(p)=(I*\mu)(p)=\sum\limits_{d\mid p}I(d)\mu(n/d)=0\)。
即 \(\mu(1)I(p)+\mu(p)I(1)=0\)，也就是 \(\mu(p)=-\mu(1)=-1\)。
- 当 \(k>1\) 时：
和上文类似，有：
因为 \(p^k>0\)，所以 \(e(p^k)=0\)，所以有 \(\sum \limits_{i \in [0,k]}\mu(p^i)=0\)，因为 \(\mu(1)=1,\mu(p)=-1\)，所以有 \(\sum\limits_{i\in[2,k]} \mu(p^k)=0\)。
考虑归纳法：
-
当 \(k=2\) 时：\(\mu(p^2)=0\)；
-
当 \(k>2\) 时：\(\mu(p^k)=-\sum\limits_{i\in[2,k-1]}\mu(p^i)=0\)。
综上，当 \(k>1\) 时， \(\mu(p^k)=0\)。
由积性函数的性质可以得到：
- 当 \(n\) 的任意一个质因子的次数超过一时，\(\mu(n)=0\)。
- 不满足第一条前提下，当 \(n\) 有 \(m\) 个质因子时，\(\mu(n)=(-1)^m\)。
接下来我们正式进入莫比乌斯反演。
- 嵌入式莫比乌斯反演（最常用）
因为 \(\mu * I =e\)，所以有 \(\sum \limits_{d \mid n}\mu(d)=[n=1]\)。
又因为 \([n \mid m][n /m=1]=[n=m]\)。
所以有 \([n \mid m]\sum \limits_{d \mid (n/m)} \mu(d)=[n=m]\)。
- 因数的莫比乌斯反演
若 \(F(n)=\sum \limits_{d \mid n} f(d)\)，那么有 \(f(n) = \sum \limits_{d \mid n}\mu(d)F(n/d)\)。
证明：显然就是 \(f=\mu*F\)。
这也是最开始我们提到的例子。
- 倍数的莫比乌斯反演
若 \(F(n)=\sum \limits_{n \mid d}f(d)\)，那么有 \(f(n)=\sum_\limits{n \mid d}\mu(d/n)F(d)\)。
也可以记做 \(F(n)=\sum \limits_{k \in N} f(kn)\) 或 \(f(n) = \sum \limits_{k \in N} F(kn)*\mu(k)\)。
证明：
如果你没有理解，这有一些解释：
-
关于第三步：因为在第二步得到的式子中，\(k\) 的取值是没有限制的，并且式子中那种不是卷积形式的式子不是很好推，于是考虑交换求和号，来使式子变成我们熟悉的卷积形式。
-
关于第五步：这里应用了嵌入式反演，因为条件都放到求和号内所以不容易看出来。
因为莫比乌斯是一个积性函数，所以它可以使用线性筛在 \(O(n)\) 的时间内预处理出不超过 \(n\) 的函数值。
Part 3：整除分块
整除分块解决的问题是：求一个形如 \(\sum \limits_if(i)\times \lfloor\dfrac{n}{i}\rfloor\) 的值，其中 \(f\) 是任意积性函数。
首先你需要知道若干个事实：
-
对于 \(\lfloor \dfrac{n}{i}\rfloor(i \le n)\)，这个表达式不同的值只有 \(O(\sqrt n)\) 个（约为 \(2\sqrt n\)）；
-
对于上述表达式，表达式值相等的 \(i\) 一定是一段连续区间。
-
对于一段值为 \(x\) 的区间，它的右端点一定是 \(\lfloor \dfrac{n}{x} \rfloor\)。
然后我们就暴力遍历每一个块，然后每一块内 \(\lfloor \dfrac{n}{i} \rfloor\) 的值都是一定的，然后我们就考虑处理 \(f\) 的部分，注意到我们要求的是 \(f\) 的一段区间和，于是可以通过某些处理求和（数学推导、前缀和）。
如果求函数区间和的时间复杂度为 \(O(1)\)，那么整除分块的时间复杂度是 \(O(\sqrt n)\)。
欧几里得
整体感知
欧几里得算法分成四部分：
-
欧几里得算法；
-
扩展欧几里得算法；
-
类欧几里得算法；
-
万能欧几里得算法；
这四个算法的核心思想都是：通过数学推导使得问题规模减小。
欧
就是辗转相除法求 gcd。
int gcd(int x,int y){return y ? x : gcd(y,x%y);}
扩欧
扩欧是一种用于求关于 \(x,y\) 的方程 \(ax+by=c\) 的一组整数解的算法。
首先，该方程存在整数解的充要条件是 \((a,b) \mid c\)，因为你可以给方程两边同时除 \((a,b)\)，然后方程左边一定是整数。
所以，方程可以转化为 \(ax+by=(a,b)\)（你可以通过给 \(x,y\) 同时乘 \(\dfrac{c}{(a,b)}\) 得到原方程的解）。
然后我们找一组 \(x_1,y_1\)，使得 \(bx_1+(a\bmod b)y_1=(b,a \bmod b)\)。
因为 \((a,b)=(b,a \bmod b)\)，因此有：\(ax+by=bx_1+(a\bmod b)y_1\)。
因为 \(a \bmod b=a-(\lfloor \dfrac{a}{b} \rfloor \times b)\)，所以有 \(ax+by=bx_1+(a-(\lfloor \dfrac{a}{b} \rfloor \times b))y_1=ay_1+b(x_1-\lfloor \dfrac{a}{b} \rfloor y_1)\)。
然后我们就有 \(x=y_1,y=x_1-\lfloor \dfrac{a}{b} \rfloor y_1\)，然后就可以递归的求解。
同时，我们也可以扩欧来求解同余方程。
显然地，我们可以把 $ ax \equiv b \pmod n$，转化为 \(ax+ ny = b \mod n\)。
类欧
类欧几里得算法是处理对于对一段连续的 \(i\)，求和类似 \(\lfloor \dfrac{ai+b}{c} \rfloor\) 的问题。
我们从一个常见形式入手：求 \(f(a,b,c,n)=\sum \limits_{i=0}^n \lfloor \dfrac{ai+b}{c} \rfloor\)。
首先，我们来一点预备知识：
-
对于 \(a,b,c \in Z\)，若 \(a < \lceil\dfrac{b}{c}\rceil\)，则 \(a < \dfrac{b}{c}\)。说明：因为 \(a\) 是整数，所以有 \(a \le \lceil\dfrac{b}{c}\rceil-1< \dfrac{b}{c}\) 。
-
对于 \(a,b,c \in Z\)，若 \(a > \dfrac{b}{c}\)，则 \(a > \lfloor \dfrac{b}{c} \rfloor\)。证明类似上式，不再赘述。
-
\(p=\sum \limits_{i=0}^{p-1} 1\)，很显然，对吧。
-
\(\sum \limits_{i=1}^n \sum \limits_{j=1}^{i} g(i,j)=\sum \limits_{j=1}^n \sum \limits_{i=1}^{n} g(i,j) \times [i \ge j]\)，其实就是把第一个求和符号对第二个求和符号的限制条件单独拿出来，然后就两个符号就独立了，因此我们可以任意调整顺序。
-
\(a=\lfloor\dfrac{a}{c}\rfloor c+(a \bmod c)\)，就是把一个数写成除一个数商和余数的形式。
请记住上面的内容，这些式子对我们接下来的推到有关键作用。
首先，我们考虑对 \(a,b\) 对 \(c\) 取模，然后我们就可以只讨论 \(0 \le a,b < c\) 的情况：
现在我们来考虑转化后的情况，我们设 \(m=\lfloor \dfrac{ai+c}{b} \rfloor\)，那么有 \(\sum \limits_{i=0}^n \lfloor \dfrac{ai+b}{c} \rfloor=\sum \limits_{i=0}^n \sum \limits_{j=0}^{m-1}[j<\lfloor \dfrac{ai+b}{c} \rfloor]\)。我们考虑对括号内的东西进行分析。
然后我们得到这个结论再回去简化 \(f\)：
这就回到了我们之前讨论的情况。我们回顾这个过程，实质上就是对 \(a,c\) 进行辗转相除。如果我们在 \(m=0\) 是终止算法，时间复杂度为 \(O(\log \min(a,c,n))\)。