Table of Contents

1. Algorithm
2. Review
   1. 基本数论记号
      1. 除法和除数
      2. 素数和组合数
      3. 除法理论，余数和模相等
      4. 定理 31.1（除法定理）
      5. 公因子和最大公因数
      6. 定理
      7. 引理
      8. 引理
      9. 引理
3. Tips
4. Share
   1. 多个家族

Algorithm

Crane: http://poj.org/problem?id=2991

https://dreamume.medium.com/poj-crane-94e6c0d3b7fb

Review

算法导论第31章 数论算法

数论曾经被认为在纯数领域是非常优美但没有太大用处的一个分支。今天数论算法被广泛使用，尤其是基于大素数的加密方案的发明。这些方案很灵活因为我们可容易地找到大素数，且它们是安全的因为我们不知道如何有效地分解大素数的乘积（或解决相关问题，比如计算离散对数）。本章呈现一些数论和相关算法

输入的大小和算术计算的成本

因为我们将关注于大整数，我们需要调整我们如何认为输入的大小和基本算术操作的成本

在本章中，一个大输入典型地表示一个输入包含大整数而不是指包含很多整数。这样，我们将度量输入的大小用输入需要的比特位数表示，而不是输入的整数个数。一个带整数输入 $a_ {1}, a_ {2}, \ldots, a_ {k}$的算法是一个多项式时间算法如果它运行在 $\lg{a_ {1}}, \lg{a_ {2}}, \ldots, \lg{a_ {k}}$的多项式时间内，即以输入的二进制长度的多项式

在本书的大部分时候，我们方便地认为基本算术操作（乘、除或计算余数）为基本操作花费一个单位时间。通过统计算法执行的这些算术操作的数量，我们有一个计算机上算法实际运行时间的合理估计的基础。然而，当输入很大时基本操作为耗时的。度量一个数论算法需要多少比特位操作是比较方便的。在这样的模型中，乘两个 $\beta$位整数需要 $\Theta(\beta^{2})$个位操作。相似地，我们除一个 $\beta$位整数或求 $\beta$位整数的余数需要 $\Theta(\beta^{2})$。有更快的方法。例如，简单的乘两个 $\beta$位整数的分治法为 $\Theta(\beta^{\lg{3}})$，已知最快的方法需要 $\Theta(\beta \lg{\beta} \lg{\lg{\beta}})$。对实际的目标，$\Theta(\beta^{2})$算法通常最好，且我们将使用这个边界作为我们分析的基础

本章中我们将一般化地分析算法用它们需要的算术操作数量和位操作数

基本数论记号

本节提供基本数论记号的简单回顾

除法和除数

一个整数被另一个除的记号是数论的关键。记号 $d | a$（读作d除a）表示a = kd，k为某个整数。每个整数都能除0。如果a > 0且 $d | a$，则 $| d | \le | a |$。如果 $d | a$，则我们也说a是d的倍数。如果d不能除a，则我们记为 $d \nmid a$

如果 $d | a$ 且 $d \ge 0$，我们说d是a的一个除数，注意 $d | a$当且仅当 $-d | a$，这样定义除数非负不失一般性。一个非零整数a的除数至少为1但不大于 $| a |$。例如，24的除数为1, 2, 3, 4, 6, 8, 12和24

每个正整数a可被1和a整除。其他的除数被称为a的因子。例如，20的因子有2，4，5和10

素数和组合数

一个a > 1的整数其除数只有1和a被称为一个素数。素数有许多特性且在数论中扮演重要的角色。前20个素数，为

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71

一个a > 1的整数不是素数则称为组合数。例如，39是组合数因为 $3 | 39$。我们称整数1为单位，它不是素数也不是组合数。相似地，0和所有负整数也不是素数和组合数

除法理论，余数和模相等

给定一个整数n，我们可分区整数为n的乘积和非n的乘积。许多数论基于根据除n的余数分类非n的乘积来进行分区。如下定理提供该提炼的基本

定理 31.1（除法定理）

对任意整数a和任意正整数n，存在唯一的整数q和r使得 $0 \le r < n$ 且 $a = qn + r$

值 $q = \lfloor a / n \rfloor$是除法的商。值r = a mod n 是除法的余数。我们有 $n | a$当且仅当 a mod n = 0

我们可根据模n的余数分区整数位n相等类。模n的相等类包含一个整数a

$[a]_ {n} = \{ a + kn: k \in \mathbb{Z} \}$

例如，$[3]_ {7} = \{ \ldots, -11, -4, 3, 10, 17, \ldots \}$，我们可记这个集合为 $[-4]_ {7}$ 和 $[10]_ {7}$。所有这些相等类的集合为

$\mathbb{Z}_ {n} = \{ [a]_ {n}: 0 \le a \le n - 1 \}$

当你看到定义

$\mathbb{Z}_ {n} = \{0,1,\ldots, n-1\}$

你应该明白0表示$[0]_ {n}$，1表示 $[1]_ {n}$等等，每个类用它最小的非负元素代表

公因子和最大公因数

如果d是a和b的除数，则d是a和b的公因数。例如，24和30的公因数有1，2，3和6

公因数一个重要的属性是

$d | a 且 d | b \Rightarrow d | (a + b), d | (a - b)$

更一般化地，我们有

$d | a 且 d | b \Rightarrow d | (ax + by)$

x和y是任意整数。同样，如果 $a | b$则 $| a | \le | b |$或b = 0，则有

$a | b 且 b | a \Rightarrow a = \pm b$

两个整数a和b的最大公因数，a和b不同时为0，我们记为gcd(a, b)。如果a和b都不为零，则gcd(a, b)为1到$min(| a|, | b |)$之间的整数，我们定义gcd(0,0)为0

gcd函数有如下基本属性：

$gcd(a, b) = gcd(b, a)$

$gcd(a, b) = gcd(-a, b)$

$gcd(a, b) = gcd(| a |, | b |)$

$gcd(a, 0) = | a |$

$gcd(a, ka) = | a |, k \in \mathbb{Z}$

定理

如果a和b为任意整数，不全为零，则gcd(a, b)是a和b的线性组合 $\{ax + by: x, y \in \mathbb{Z} \}$集合中的最小正整数元素

证明 设s为a和b的线性组合中最小的正整数，s = ax + by，$x, y \in \mathbb{Z}$。设 $q = \lfloor a / s \rfloor$。有

$\begin{aligned} a \text{ mod } s &= a - qs \\ &= a - q(ax + by) \\ &= a(1 - qx) + b(-qy) \end{aligned}$

这样a mod s是a和b的线性组合。但，因为 $0 \le a \text{ mod } s < s$，我们有 a mod s = 0，因为s是现象组合中最小的正整数。因此，我们有$s | a$，类似地，我们可得到 $s | b$。则，s是a和b的公因数，这样 $gcd(a, b) \ge s$。从之前的公式中我们得到 $gcd(a, b) | s$，因为gcd(a, b)能被a和b整除，且s是a和b的线性组合。但 $gcd(a, b) | s$且s > 0意味着 $gcd(a, b) \le s$。组合 $gcd(a, b) \ge s$和$gcd(a, b) \le s$我们得到gcd(a, b) = s。这样我们得到结论s是a和b的最大公因数

引理

对任意整数a和b，如果 $d | a$和 $d | b$，则 $d | gcd(a, b)$

引理

对所有整数a和b和任意非负整数n，

$gcd(an, bn) = n \operatorname{gcd}(a, b)$

证明 如果n = 0，则显然成立。如果n > 0，则gcd(an, bn)是集合 $\{anx + bny: x, y \in \mathbb{Z} \}$中最小的正整数元素，其是集合 $\{ax + by: x, y \in \mathbb{Z} \}$中最小正整数元素的n倍

引理

对所有正整数n，a和b，如果 $n | ab$且gcd(a, n) = 1，则 $n | b$

Tips

看极客课程的一些感想

首先是《趣谈网络协议》里的一句话：“复杂的程序都要分层。”虽然这门课主要讲的是网络分层模型，但分层的思想在程序架构中普遍存在。现在复杂的程序或库设计时都会有先设计出一个架构，有一个架构图，没有架构而谈模块设计、设计模式几乎是肯定不行的。分层架构是最常见的，往往层分好了，模块也就知道怎么划分了

架构是非常重要的，如果软件或库的设计没有架构，那肯定是不太好的。分层架构可说是架构里的万能钥匙，简单实用，威力巨大。我就从网上摘录出别人总结的语句就好了：

1. 分层架构（layered architecture）是最常见的软件架构，也是事实上的标准架构。如果你不知道要用什么架构，那就用它
2. 这种架构将软件分成若干个水平层，每一层都有清晰的角色和分工，不需要知道其他层的细节。层与层之间通过接口通信
3. 虽然没有明确约定，软件一定要分成多少层，但是四层的结构最常见

其实分层的思想可以用在很多地方，它应该是常备的解决问题的工具之一，如果遇到难题不知道怎么解决，可以想一想是否可分层处理。因有人说过：

“All problems in computer science can be solved by another level of indirection” – David Wheeler

通俗地说，就是所有的计算机科学上的问题都可以通过加一个抽象层解决

其次是《10x程序员工作法》中谈到了亚马逊CTO介绍亚马逊是如何开发一项产品的，开发顺序为：

1. 写新闻稿
2. 写FAQ（常见问题解答）
3. 写用户文档
4. 写代码

我也非常认同，但角度可能不一样。特别是对于通常的开发过程中，写代码应该是最后的步骤，其实是相对最不重要的，前面的写文档很重要，因为没有文档上来就写代码，往往会写到一半就被卡住。通常是因为并没有想清楚或考虑的不周全，而你的想法不落到纸上写出来，有些地方是看不出来的。当你都想好了，文档出来了，再写代码，那应该是最简单最轻松地事情

Share

Families of sets

https://crypto.stanford.edu/pbc/notes/zdd/family.html

假设我们有一个收集，或家族，为字母的集合，比如 $\{ \{ A, B, X, Y, Z\}, \{A, C, X, Y, Z \} \}$（一个家族包含两个集合）。如何在电脑上表示一个家族以便容易操作它们？我们表示执行典型的集合理论操作比如找到某些集合的并或交，测试成员，且测试是否一个给定集合跟我们的集合之一是否相等

最明显的解决方案是用位域：使用26个比特位来表示一个集合，当我们设置第i位当且仅当集合包含第i个字母。这样我们的例子家族会表示为 $\{1100 \ldots 0111, 1010 \ldots 0111\}$

多数情况下这是个好的解决方案。它容易理解和实现。计算并、交、集合的不同等都简化为执行相关地位操作。我们可在哈希表中存储我们的集合来快速测试是否我们有一个给定的集合

但当一个家族总是包含不相交集，Galler-Fischer表示法更有效

多个家族

假设我们有两个或多个集合家族。例如，我们可能有家族 $F = \{\{A, B, X, Y, Z \}, \{ A, C, X, Y, Z\}\}$及$G = \{\{W, X\}, \{C, D, E\} \}$。在一些问题中，我们想要找到所有集合，其是F中某些集合和G中的某个集合的并，我们记为 $F \sqcup G$。在我们的例子中，

$F \sqcup G = \{\{ A, B, W, X, Y, Z\}, \{A, C, W, X, Y, Z\}, \{A, B, C, D, E, X, Y, Z\}, \{ A, C, D, E, X, Y, Z\} \}$

结果中有4个集合因为我们在F中有2个选择，G中有2个选择，且结果中的元素没有相同的

如果我们使用位域来表示集合，计算 $F \sqcup G$意味着我们必须迭代F中所有集合和G中所有集合来获得其并。在每个并之后，我们必须检查重复。例如，$\{\{A \}, \{B\}\} \sqcup \{\{A\},\{B\}\} = \{\{A\}, \{B\}, \{A, B\}\}$只有3个元素，而不是4个

交操作跟并操作类似，我们有 $F \sqcap G$，为 $\{\{A\}, \{B\}\} \sqcap \{\{A\}, \{B\}\} = \{\{A\}, \{B\}, \phi \}$

如果在家族中执行少量操作这是可以的。但许多问题在于家族代数上很重，且位域的代价变得不可接受。对此，我们需要家族集合中有许多相同元素这一点