Feb 16

《初等数论》读书笔记：同余

Art of Science 1 Comments

这里的同余包含了同余和同余方程两个章节。

基本的同余概念可以从带余除法中推导出来。使用带余除法，我们可以得到同余式的相关运算性质。

接下来，我们引入同余类和剩余系的概念。剩余系主要是介绍了既约剩余系。我们从既约剩余系的定义中引出了Euler函数。Euler函数是一个积性函数，也就是说如果(m1,m2)=1，那么$\varphi(m_1m_2)=\varphi(m_1)\varphi(m_2)$。Euler函数有如下的计算式 $\varphi(m)=m\prod_{p|m}(1-\frac{1}{p})$，特别的，当m=pk时，我们有$\varphi(p^k)=p^{k-1}(p-1)$。我们还有\sum_{d|m}\varphi(d)=m，我们可以从中看出Mobius函数的一点影子。

接下来，我们由一个性质得到了一个重要的定理：Fermat-Euler定理。这个性质是，对于一个模m，它的任何一个既约剩余系中所有元素的乘积模m是相同的，也可以表述为(a,m)=1时，x遍历m的既约剩余系当且仅当ax遍历m的既约剩余系。我们得到$a^{\varphi(m)}\equiv 1\pmod{m}$，以及当m=p时，对于任意的a，我们有$a^p\equiv a\pmod{p}$。前面的式子被称为Fermat小定理，后面的式子被称为Euler定理。

Wilson定理是如下的内容$r_1\cdots r_{p-1}\equiv -1\pmod{p}$，也就是对于一个素数p>3，它的既约剩余系中所有数的乘积模p为-1。特别的，我们有$(p-1)!\equiv -1\pmod{p}$。事实上，p不取1,2,4,pk,2pk时，p的既约剩余系的积模p得1。Wilson虽然不能用来高效地检验素数，但是可以被用来简化运算。

同余方程是多项式同余的形式。其最简单的形式是一次同余方程。我们可以用带余除法和辗转相除法得到其解。中国剩余定理用来求解一次同余方程组。对于一个一次同余方程组$x\equiv a_j\pmod{m_j},1\leq j\leq k$，这里m1,...,mk两两既约。那么其解为$x\equiv M_1M_1^{-1}a_1+\cdots+M_kM_k^{-1}a_k\pmod{m}$，m=m1...mk，m=mjMj，以及$M_j^{-1}$是Mj模mj的逆。这个解的正确性容易带入验证。如果m1,...,mk并非两两既约，则可以化为各个方程都是模pk的形式更加方便。

关于模为素数的二次同余方程，我们只需要讨论$x^2\equiv d\pmod{p}$的形式。对于模p，如果一个d能使得方程有解，那么我们称d为模p的二次剩余；否则d就是模p的二次非剩余。我们可以用Euler判别法来进行判断。如果$d^{(p-1)/2}\equiv 1\pmod{p}$，那么d就是模p的二次剩余；如果$d^{(p-1)/2}\equiv -1\pmod{p}$，那么d就是模p的二次非剩余。

我们还可以引进Legendre符号和Jacobi符号来进行进一步的研究。Gauss二次互反律也是进一步的探讨对象。具体内容可以参见原书或者nmbr.rar。

Feb 13

《初等数论》读书笔记：整除

Art of Science 0 Comments

一上来作者介绍了Peano公理。这个公理告诉我们，自然数就是一个有起点的、存在后继的无限整数集合。自然数的性质都可以通过这个抽象的定义来推导。我们一般使用1,2,3,...，是因为它本身具有代表性。至于0的问题，一般在不涉及的情况下不考虑。从Peano公理我们得到了数学归纳法和两个自然数的原理：最小和最大自然数原理。数学归纳法在数论当中可以用来证明多项的命题，也可以用来证明取值范围是固定连续整数域的恒等式或者命题。

接下来是整除的概念，我们一般是把它和带余除法结合起来看。从基本定义我们就可以推导很多有用的性质。从整除我们得到一类非常有用的数：素数。素数具有很多的性质。关于素数的判定也是一个很重要的课题，一般而言我们有试除法、Fermat素性检验、Miller-Rabin素性检验。A.K.S算法是第一个被证明的可以在多项式时间内检验素数的算法。

接下来作者介绍了公约数和公倍数的理论。我们又得到了互素的概念。这在书中仅仅是一个先头的简单介绍，作者接着引进了带余除法的概念。这是一个非常有用的概念，我们可以通过它进行很多讨论余数的证明。整数分类也是来自于带余除法。有了带余除法的概念之后，我们就可以讨论很多情况下余数的性质。带余除法是初等数论中极其重要的内容。

接下来就是辗转相除法。这也是一个来自于带余除法的内容。

我们现在可以建立最大公约数理论。带余除法、辗转相除法和整系数线性组合是3种很容易被引进的方法。我们需要了解的是，一个集合中数的最大公约数就是这些数的整系数线性组合中最小的那一个，也就是$(a_1,\cdots,a_k)=\min\{s=a_1x_1+\cdots+a_kx_k:x_j\in Z(1\leq j\leq k),s>0\}$。

现在进入到了算术基本定理，我们现在可以用素数的性质来对整数进行分析。由于算术基本定理的存在，我们一定可以通过分析素数的性质来得到相关整数的性质。这里需要介绍一下除数和函数$\sigma(n)=\prod_{j=1}^{r}\frac{p_j^{a_j+1}-1}{p_j-1}$。

对于本章最后的[x]函数的分析，就不再过多的叙述，因为都是很普通的内容。而对于n!的分解式，要能够体会其中蕴含的缩小规模的递归思想。

最后是容斥原理和$\pi(x)$的分析。容斥原理更多的是使用在组合数学当中。而$\pi(x)$的计算需要相应的推导，具体内容可以参见书中。或者可以参见我的另外一个笔记：nmbr.rar。

Feb 3

最短增广路在网络流中的应用

Art of Science 0 Comments

最短增广路，顾名思义，就是一条增广路，而且还是所有增广路中最短的一条。要求出最短增广路也十分容易，只要在残量网络中求出源点到汇点的最短路就可以了（所有边的长度为1）。

求出了最短增广路，我们就可以沿着它对网络进行增广，而且可以证明，如果只要求最大流，最多经过n（n为总结点数）次增广，就可以求出最大流。实现也非常简单，由于所有边的长度为1，所以只需要使用宽搜。使用最短增广路的方法求最大流，其实也是Ford-Fulkerson方法的一种，这种方法的特点是每次找出一条残量网络中的增广路径并进行增广。整个过程中满足流的网络的三个性质：容量限制、反对称性、流守恒性。

如果不知道什么是残量网络（或者又被叫做残留网络），请看下面的解释。

  • 残量：容量－流量。
  • 残留边：有残留容量的边成为残留边
  •  残留网络：由网络的点集、残留边集构成残留网络。

这里我们需要注意一点，宽搜的结果如果可以为后面所利用的话，我们就可以写出一种新的求最大流的算法：SAP，全称Shortest Augmenting Path Algorithm。其时间复杂度为O(n2m)。在实践中，这种算法效率还是比较高的，而且性价比相当好（我一般都会使用它）。

在SAP中，定义每个点的距离标号，即残留网络中点到汇点的距离。然后，只需要在距离标号相邻的点间寻找增广路径。如果从一个点出发没有可行边，就对该点进行重标记，然后并回溯（类似预流推进算法）。

可行边就是说，存在一条边<i,j>，当且仅当ri,j>0且di=dj+1时，边是容许边，我们的算法只考虑容许边（这里d指距离标号，r指残量网络中的流量）。

算法的一开始，我们从汇点t进行一次宽搜求出距离标号（或者也可以不进行预处理，直接赋值为0，因为随着重标记的过程，距离标号会自行调整），然后从源点s开始递归操作（或者也可以不递归，因为算法本身并不繁琐）。对于一个点i，如果存在容许边<i,j>，当j是汇点时增广并从源点开始递归，否则就令i是j的前驱，并递归j。否则对i重标号，使得di=min{dj|ri,j>0}+1，并回溯。当$d_s\geq n$时算法停止，此时不存在任何一条增广路。

当然我们可以参考预流推进，对它进行间隙优化。同时还有一个叫做当前弧的优化，采用后速度也有一定的提升。而且，采用前向星的储存方式会更好。

我们也可以用最短增广路来求最小费用最大流，原理不需要再阐述了，如果是用增广路算法来求最小费用最大流，就是要找一条费用最少的路径来进行增广。当然可以套用最短增广路的方法来做。 

Feb 2

稳定婚姻问题(Stable Marriage Problem)

Art of Science 0 Comments

问题概述：有n个女生和n个男生，每位女生按照她的偏爱程度将男生排序，同时每位男生也按照自己的偏爱程度将女生排序，然后将这n个女生和n个男生配成完备婚姻。

如果存在两位女生A和B，两位男生a和b，使得A和a结婚，B和b结婚，但是A更偏爱b而不是a，b更偏爱A而不是B，则这 个婚姻就是不稳定的。反之，这个婚姻就是稳定的。

可以通过证明，得到每一个n女n男的社团，都存在稳定婚姻的结论。但是这种情况只在异性的社团中存在。也就是说在同性的社团里面，稳定婚姻的存在性将不再被保证。下面是一种简单的稳定婚姻的算法。

Gale-Shapley 算法： 

while存在男人m是自由的且还没对每个女人都求过婚
   选择这个男人m
   令w是m的优先表中还没求过婚的最高排名的女人
   if w 是自由的
       (m,w)变成约会状态
   else
       w当前与m1约会
       if w更偏爱m1而不爱m
           m保持自由
       else
           w更偏爱m而不爱m1
           (m,w)变成约会状态
           m1变成自由
       endif
   endif
endwhile

一道关于稳定婚姻问题的题目：ZJU 1576 Marriage is Stable。

Feb 2

二分图最大权完美匹配的KM算法

Art of Science 0 Comments

 二分图最大权完美匹配KM算法是在一个二分图里，求一个最大权匹配，但是要求这个匹配必须是完美匹配。如果匹配不一定是完美匹配，那么似乎只能将其转化为最小费用最大流来做了。我们可以使用KM算法对任意带权（无论正负权）二分图求最大/最小权完美匹配，它的算法复杂度是O(n3)，但是如果写得不好会变成O(n4)。

KM算法是通过给每个顶点一个标号（我们有时称之为顶标）来把求最大权匹配的问题转化为求完备匹配的问题的。我们令二分图中X部的节点的顶标为Ai，Y部的节点的顶标为Bi。X部与Y部节点之间的权值为Wi,j，那么，在算法进行的过程中，我们必须始终保持$A_i+B_i\geq W_{i,j}$成立。因为KM算法的正确性基于以下定理：

若由二分图中所有满足Ai+Bi=Wi,j的边 (i,j)构成的子图（称做相等子图）有完备匹配，那么这个完备匹配就是二分图的最大权匹配。

初始时为了使$A_i+B_i\geq W_{i,j}$成立，令Ai为所有与Xi顶点关联的边的权值的最大值，令Bi=0。如果当前的相等子图没有完备匹配，就需要修改顶标以使扩大相等子图，直到相等子图具有完备匹配为止（这样就可以求出最大权匹配）。

如果当前相等子图找不到完备匹配，那么是因为对于某个X顶点，我们找不到一条从它出发的交错路。这时我们获得了一棵交错树，现在我们把交错树中X部的顶点的顶标全都减小某个值d，Y部的顶点的顶标全都增加d，就可以使得至少有一条新边进入相等子图。这里d=min{Ai+Bi-Wi,j}，而且Xi在交错树中，Yi不在。

但是如果仅仅是这样，用朴素的方法实现，算法复杂度是O(n4)。我们给每个Y部的顶点一个“松弛量”slack，每次开始找增广路时松弛量初始化为无穷大。在寻找增广路的过程中，检查边(i,j)时，如果它不在相等子图中，则让slackj变成原值与Ai+Bi-Wi,j的较小值。这样，在修改顶标时，取所有不在交错树中的Y顶点的slack值中的最小值作为d值即可。但还要注意一点：修改顶标后，要把所有的slackj值都减去d。经过这样一个优化实现后，算法复杂度就变成了O(n3)。