Question

高者抑之，下者举之；有馀者损之，不足者与之。《老子》

Residue

整数除法：被除数除以除数得到商数与馀数。分堆到底为止。

可以分堆、补堆任意次数的时候，除数就变成了“模数”，馀数就变成了“留数”。

馀数只有一个，留数有无限多个。只要随便求出一个馀数，不断加减模数，就得到各个留数；各个留数皆平等，任选一个当代表都行，通常是写最接近零、大于等于零的那一个。一般使用≡全等符号表示各个留数两两之间的平等关係。

中文习惯把留数也称作馀数。以下皆用馀数称呼留数。

中英对照

被除数 dividend
除数 divisor
商数 quotient
馀数 remainder
模数 modulus
留数/残数/残值/馀数 residue
全等/同馀 congruence

馀数运算

residue 一般是指“残值”，例如残值定理；在馀数系统，则是指“馀数”，是一个实际数值。

congruence 一般是指“全等”，例如三角形全等；在馀数系统，则是指“同馀”，是一种抽象概念，是一个运算符号。

计算学家重视数值，因此演算法书籍喜爱讨论 residue；数学家重视性质，因此数学书籍喜爱讨论 congruence。

实数运算，等于=不是主角，加减乘除才是主角；馀数运算，同馀≡当然也不是主角，加减乘除才是主角。

因此接下来将要讨论 residue 的加减乘除。

+

模数相同时，馀数可相加。

8 (mod 3) + 7 (mod 3) ≡ 15 (mod 3)
8 (mod 3) + 7 (mod 3) + 6 (mod 3) ≡ 21 (mod 3)

模数相同时，mod 符号可以精简成一个，写在式子后面。

8 + 7 ≡ 15 (mod 3)
8 + 7 + 6 ≡ 21 (mod 3)

馀数加法实际上是“无限多个”加“无限多个”等于“无限多个”。这三项当中，任取一个馀数当代表都行，等式皆成立。然而实际计算时，大可不必想得如此複杂，就是加与模，求得最接近零、大于等于零的那一个馀数。

延伸阅读：模数不一致的加法

鸡肋。穷举每一种馀数并且相加。

  1 (mod 4) + 1 (mod 6)
≡ ⋯ ∪ 
  { 1 (mod 4) + -5 } ∪ 
  { 1 (mod 4) +  1 } ∪ 
  { 1 (mod 4) +  7 } ∪ 
  ⋯
≡ { 0 (mod 4) } ∪ { 2 (mod 4) }

−

模数相同时，馀数可相减。

8 - 7 ≡ 1 (mod 3)
8 - 7 - 6 ≡ -5 (mod 3)

UVa 10787

×

馀数可以乘上整数倍率，等同于连加。

8 (mod 5) × 7 ≡ 56 (mod 5)
8 (mod 5) × 7 × 6 ≡ 336 (mod 5)

倍率可以推广成馀数。换句话说：模数相同时，馀数可相乘。

8 (mod 5) × 7 (mod 5) ≡ 56 (mod 5)
8 (mod 5) × 7 (mod 5) × 6 (mod 5) ≡ 336 (mod 5)

模数相同时，mod 符号可以精简成一个，写在式子后面。

8 × 7 ≡ 56 (mod 5)
8 × 7 × 6 ≡ 336 (mod 5)

直接套用“ 整数乘法 ”的演算法。

UVa 10787

÷

已知一乘数、乘积，求另一乘数。

☐ × 7 ≡ 21 (mod 5)
8 × ☐ ≡ 56 (mod 5)

移项一下，即是除法。

21 ÷ 7 ≡ 3 (mod 5)
56 ÷ 7 ≡ 8 ≡ 3 (mod 5)  

馀数除法、实数除法，概念完全不同。实数除法具备“分成几等份”的意义，而馀数除法不具备这种意义！馀数除法被定义成馀数乘法的反运算。馀数除法的本质是乘法式子解未知数。

任选一个馀数当代表，儘管看似无法整除，却存在计算结果。

☐ × 7 ≡ 21 (mod 5)  ->  3 × 7 ≡ 21 (mod 5)  ->  21 ÷ 7 ≡ 3 (mod 5)
☐ × 7 ≡ 16 (mod 5)  ->  3 × 7 ≡ 16 (mod 5)  ->  16 ÷ 7 ≡ 3 (mod 5)
☐ × 7 ≡ 11 (mod 5)  ->  3 × 7 ≡ 11 (mod 5)  ->  11 ÷ 7 ≡ 3 (mod 5)
☐ × 7 ≡ 6  (mod 5)  ->  3 × 7 ≡ 6  (mod 5)  ->   6 ÷ 7 ≡ 3 (mod 5)
☐ × 7 ≡ 1  (mod 5)  ->  3 × 7 ≡ 1  (mod 5)  ->   1 ÷ 7 ≡ 3 (mod 5)

有时候也可能无解、多解。

☐ × 2 ≡ 3 (mod 4)   ->  3 ÷ 2 ≡ ☐ (mod 4)   ☐不存在
☐ × 4 ≡ 5 (mod 10)  ->  5 ÷ 4 ≡ ☐ (mod 10)  ☐不存在
☐ × 3 ≡ 0 (mod 6)   ->  0 ÷ 3 ≡ ☐ (mod 6)   ☐是 0 或 2
☐ × 3 ≡ 3 (mod 12)  ->  3 ÷ 3 ≡ ☐ (mod 12)  ☐是 1 或 5 或 9

究竟如何计算馀数除法呢？数学家发明了倒数！

倒数

数学家利用等量乘法原理，建立倒数的概念。

1 ÷ 7     ≡ ☐     (mod 5)   移项之后的式子
☐ × 7     ≡ 1     (mod 5)   原问题
☐ × 7 × 7 ≡ 1 × 7 (mod 5)   等号两侧同乘以“7 的倒数”
☐         ≡ 1 × 7 (mod 5)   7 乘以“7 的倒数”令它是 1，就能消掉。

数学家于是规定：原数与倒数相乘等于 1。除法变成“乘以倒数”，解决了看似无法整除的情况！

1 ÷ 7 ≡ 1 × 7 ≡ ☐ (mod 5)

预先求出倒数，便可计算馀数除法！

模 5 的时候，7 的倒数是 3。因为 7 × 3 ≡ 1 (mod 5)。
7 ≡ 3 (mod 5)

21 ÷ 7 ≡ 21 × 7 ≡ 21 × 3 ≡ 63 ≡ 3 (mod 5)
20 ÷ 7 ≡ 20 × 7 ≡ 20 × 3 ≡ 60 ≡ 0 (mod 5)
 3 ÷ 7 ≡  3 × 7 ≡  3 × 3 ≡  9 ≡ 4 (mod 5)
 2 ÷ 7 ≡  2 × 7 ≡  2 × 3 ≡  6 ≡ 1 (mod 5)
 1 ÷ 7 ≡  1 × 7 ≡  1 × 3 ≡  3 ≡ 3 (mod 5)

实数系统的倒数，就是分子与分母颠倒。馀数系统的倒数，可以运用“ 辗转相除法 ”求得。

倒数的定义
a × a ≡ 1 (mod m)

已知 a 与 m，欲求a，
使得 a × a ≡ 1 (mod m)。

取其中一个馀数当作代表，上式可以重新整理成
a × a = 1 + m × k
a × a - m × k = 1
a × a + m × (-k) = 1

再利用延伸版本的辗转相除法，
求得 a 与 m 的最大公因数（必须是 1），
并求得倍率a与(-k)。
其中a就是我们想要的“a 的倒数”。

根据辗转相除法的推导结果，如果一个数与模数的最大公因数等于一（互质），才拥有倒数。

最大公因数是 1，才能一路逆推，使得倒数的式子成立。
a × a + m × (-k) = 1
a × a - m × k = 1
a × a = 1 + m × k
a × a ≡ 1 (mod m)

换个角度来说。模数是质数，每一个数都有倒数；模数不是质数，只有跟模数互质的数才有倒数！

我不知道如何判断馀数除法是唯一解、无解、多解。

反元素（inverse element）、单位元素（identity element）

世界事物往往相对，有前就有后，有上就有下。

创造一个数学运算，往往就出现了反向运算：加法之于减法，乘法之于除法，函数之于反函数。

一般来说，正与反是能够等量相消的。用以等量相消的元素，称作“反元素”：加法的反元素是负数-x，乘法的反元素是倒数 1/x，函数的反元素是反函数 f⁻¹。所谓的“元素”，视情况是指数值、是指函数、是指矩阵、……，算是个总称。

正与反等量相消之后，成为了一个无能的、没用的元素，称作“单位元素”：加法当中，数与负数相加等于单位元素，是零；乘法当中，数与倒数相乘等于单位元素，是一；函数转换中，函数与反函数合成等于单位函数（identity function）；矩阵与反矩阵合成等于单位矩阵（identity matrix），对角线是一、其馀是零。

每当数学家创造新的数系、创造新的数学运算，就会勘查反元素、单位元素。学习这些概念后，就有了个行动纲领，就有了个标准作业流程 SOP，用以对付人类还不晓得的数学。

数学系的基础代数课程，就会提到反元素、单位元素。虽然是形而上，但是这不是什麽深奥的数学概念，读者不必自己吓自己。

^

馀数可以有整数次方，等同于连乘。

8 (mod 3) ^ 3 ≡ 8 (mod 3) × 8 (mod 3) × 8 (mod 3) ≡ 512 (mod 3)

套用“ 整数次方 ”的演算法即可。

次方可以推广成馀数，但是次方的模数不是原本模数。

“ Fermat's Little Theorem ”
若模数是质数 p，则次方的模数正是 p-1。
2 (mod 7) ^ 100 ≡ 2 (mod 7) ^ 100 (mod 6)

“ Carmichael's Theorem ”
若模数与底数互质，则次方的模数，
是模数的“Carmichael Function, λ(m)”的其中一个因数。
2 (mod 9) ^ 100 ≡ 2 (mod 9) ^ 100 (mod λ(9))

“ Euler's Theorem ”
若模数与底数互质，则次方的模数，
是模数的“Euler's Totient Function, φ(m)”的其中一个因数。
φ(m) 不精准，有多馀的因数，有些因数不可能是次方的模数。但是φ(m) 比较容易求得。
2 (mod 9) ^ 100 ≡ 2 (mod 9) ^ 100 (mod φ(9))

若模数是普通数字，则没有数学公式，只能使用穷举法求得次方的模数。

计算λ(m) 和φ(m)，需要质因数分解，旷日费时，乏人问津。况且我们也不确定是λ(m) 和φ(m) 的哪一个因数。

但是如果预先知道λ(m) 或φ(m)，就可以预先将次方值模λ(m) 或φ(m)，以加速次方运算。

预先知道 φ(9) = 6
  2 (mod 9) ^ 100
≡ 2 (mod 9) ^ 100 (mod φ(9))
≡ 2 (mod 9) ^ 100 (mod 6)
≡ 2 (mod 9) ^ 4 (mod 6)
≡ 16 (mod 9)
≡ 7 (mod 9)

UVa 374

倒数（模数是质数）

根据费马小定理，当模数为质数 p，那麽倒数即是 p-2 次方。

模数为质数 p
a ^ p         ≡ a (mod p)
a ^ (p-1)     ≡ 1 (mod p)   当 a ≢ 0 (mod p)
a ^ (p-2) × a ≡ 1 (mod p)   当 a ≢ 0 (mod p)
a = a ^ (p-2)     (mod p)   当 a ≢ 0 (mod p)，0 没有倒数

不必另外撰写辗转相除法。时间複杂度也差不多。

倒数表（模数是质数）

若模数是质数，则每一个数都有倒数！

此时可以预先建立倒数表，预先计算每一个数的倒数。建立倒数表有著较快的演算法，时间複杂度为 O(N)，N 为模数大小。大可不必逐个数字套用辗转相除法。

 p % i = p - (p ÷ i) × i
 p % i ≡   - (p ÷ i) × i           (mod p)
inv[i] ≡   - (p ÷ i) × inv[p % i]  (mod p)   i 移项到左边，p%i 移项到右边

Congruence

馀数系统的特色：有限范围

馀数系统有个非常重要的特性：数字大于等于零、不超过模数。

电脑只能处理有限范围的整数。馀数系统得发挥功效。

实数系统的加法表、乘法表
+ | 0  1  2  3 ...   × | 0  1  2  3 ...
--|-----------       --|-----------    
0 | 0  1  2  3 ...   0 | 0  0  0  0 ...
1 | 1  2  3  4 ...   1 | 0  1  2  3 ...
2 | 2  3  4  5 ...   2 | 0  2  4  6 ...
3 | 3  4  5  6 ...   3 | 0  3  6  9 ...
:   :  :  :  :       :   :  :  :  :    

馀数系统的加法表、乘法表
(mod 1)  (mod 2)    (mod 3)       (mod 4)          (mod 5)
+ | 0    + | 0  1   + | 0  1  2   + | 0  1  2  3   + | 0  1  2  3  4
--|--    --|-----   --|--------   --|-----------   --|--------------
0 | 0    0 | 0  1   0 | 0  1  2   0 | 0  1  2  3   0 | 0  1  2  3  4
         1 | 1  0   1 | 1  2  0   1 | 1  2  3  0   1 | 1  2  3  4  0
                    2 | 2  0  1   2 | 2  3  0  1   2 | 2  3  4  0  1
                                  3 | 3  0  1  2   3 | 3  4  0  1  2
                                                   4 | 4  0  1  2  3

(mod 1)  (mod 2)    (mod 3)       (mod 4)          (mod 5)
× | 0    × | 0  1   × | 0  1  2   × | 0  1  2  3   × | 0  1  2  3  4
--|--    --|-----   --|--------   --|-----------   --|--------------
0 | 0    0 | 0  0   0 | 0  0  0   0 | 0  0  0  0   0 | 0  0  0  0  0
         1 | 0  1   1 | 0  1  2   1 | 0  1  2  3   1 | 0  1  2  3  4
                    2 | 0  2  1   2 | 0  2  0  2   2 | 0  2  4  1  3
                                  3 | 0  3  2  1   3 | 0  3  1  4  2
                                                   4 | 0  4  3  2  1

连加循环

不断连加，导致循环。循环是馀数系统的重要性质！

画在圈圈内部，更清楚。

连加画在圆的等分点上，得以构造正多边形、正多角星。

连加画在数线上，得以连结到最小公倍数的概念。

当模数是连加数的倍数（连加数是模数的因数）（连加数整除模数），大多数情况无法遭遇全部数字，除非连加数、模数是一。

考虑所有情况，归纳简洁结论：连加数与模数，最大公因数不等于一（不互质），遭遇部分数字；最大公因数等于一（互质），遭遇全部数字。

简单一句话：互质，遭遇全部数字。

循环节长度等于“最小公倍数除以连加数”，也等于“模数除以最大公因数”。请读者自行按图推理。

顺带一提“与模数互质的连加数”总共有φ(m) 个。

连乘循环

不断连乘，导致循环。

加法循环，跳跃很规律；一种连加数，只有一种循环节。

乘法循环，跳跃没规律；一种连乘数，拥有各种循环节。

想要确认循环节起点、循环节长度，可以使用 Floyd's Algorithm 或 Brent's Algorithm。

乘法群

数学家倾向讨论性质优美的事物。

首先区隔“与模数互质的数字”和“不与模数互质的数字（模数的因数、不含一）”，只取前者。

“与模数互质的数字”不断相乘，绝不会得到“不与模数互质的数字（模数的因数、不含一）”，而且所有数字都位于某个循环节之内。

由于与模数互质，每个数字都只有唯一一个倒数，馀数除法亦成立！乘法正向跳跃，除法反向跳跃，双向都通。

“与模数互质的数字”暨乘法除法，性质优美，自成一格，数学家称作“ 乘法群 ”。一种模数得到一种乘法群。另类的有限范围！

顺带一提“与模数互质的数字”总共有φ(m) 个。

次方循环

连乘循环的特例。起点是零次方。

循环长度必定是λ(m) 的因数（或者是φ(m) 的某些因数）。目前没有演算法可以快速验证是哪一个因数，只能使用试误法。

原根（Primitive Root）

数学家倾向讨论性质优美的事物。

首先取出“与模数互质的数字”当作底数。引入乘法群的观点，这些底数的任意次方，仍是“与模数互质的数字”。

从中取出“遭遇全部数字”的底数。当模数是 1、2、4、p^n、2*(p^n) 才有可能（p 是大于 2 的质数），不过我不会证明。

每种次方刚好遭遇每种数字、所有数字都在同一个循环节裡面。依照遭遇顺序，重新串成一圈。

符合条件的底数，彷彿“ 单位根 ”：“1 开φ(m) 次方”、“φ(m) 次根号 1”。符合条件的底数通常只有其中几个，而“单位根”是指每一个，不尽相同，因此数学家另取一名“原根”。

原根的演算法

除了试误法，目前没有更好的演算法。

穷举各种底数 r，总共有φ(m) 种可能。
口、针对一种底数 r，穷举各种次方。
　　如果皆不等于 1，r 就是原根。
口、另一种方式：
　　质因数分解φ(m)，得到质因数 p1 p2 ... pk。
　　针对一种底数 r，穷举各种质因数 p1 p2 ... pk。
　　如果 r^(φ(m)/p1) r^(φ(m)/p2) ... r^(φ(m)/pk) 皆不等于 1，
　　r 就是原根。
　（检测各种循环节长度。φ改成λ，检测次数更少；然而λ很难算。）

求得其中一个原根，就容易求得所有原根。手法是连加循环！

求得其中一个原根之后，以此原根的某个次方（选择适当的连加数），当作新的原根，尝试遭遇所有数字。

再来一个模数更大的例子。模数是 13，取出与模数互质的数字 1 2 ... 12，总共φ(13) = 12 个。用试误法求得其中一个原根是 2，依照次方顺序重新串成一圈。找到与φ(13) = 12 互质的数字 1 5 7 11 当做连加数，以遭遇全部数字，符合原根定义！连加数总共φ(φ(13)) 个。

最后下个结论：模数 m 必须是 1、2、4、p^n、2*(p^n)，才有原根，其个数是φ(φ(m))。p 是大于 2 的质数。

阶乘循环

本人才疏学浅，不清楚。

延伸阅读：群、环、体

http://itchen.class.kmu.edu.tw/Crypto/GRF.html

数学家擅于分类性质优美的事物。此即一种分类方式，以运算符号和运算律来分类。科学味道稀薄、工程味道浓厚，不必强记。

Polynomial Residue

http://picks.logdown.com/archives

我们比较常看到馀数系统的"整数运算"
5+3=0 (mod 4)  5^-1 = 3 (mod 7) 这种的　　辗转相除法求倒数　大步小步算法　等等

而这系列文章是讲馀数系统的"多项式运算"
诸如多项式除法，多项式倒数等等
他说可以用 divide and conquer 和 fft 很快地算出来

最后他还搞出了“多项式版本的牛顿法”这个终极武器
本来牛顿法是求根 (find x , let f(x) = 0)
    x 在什麽情况下，y 会等于零？
    输入 x 是实数，输出 y 是实数，利用斜率 dy/dx，递推法，逼近根的位置
结果他把实数推广成多项式  照算不误

最后他把各种多项式运算，例如除法、次方等等，通通用牛顿法来算
把式子移项，变成"甚麽甚麽等于零"　--->  x 在什麽情况下,y 会等于 0　---> 这就求根阿
就这样　牛顿法搞定全部

Finite Field

楔子

整数，拥有质数的概念。列举质数、判断质数、质因数分解，可参考本站文件“ Prime ”。

列举质数：2, 3, 5, 7, 11, ...
判断质数：999 is not prime
质因数分解：999 = 3 × 3 x 3 x 37

整数多项式，亦拥有质式的概念。通常只讨论一元多项式（只有一个变数）。列举质式、判断质式、因式分解，更加困难。

列举质式：x, x + 1, x + 2, ...
判断质式：x² + x + 1 is irreducible polynomial
因式分解：2x² + 5x + 2 = (2x + 1)(x + 2)

馀数多项式，亦拥有质式的概念。列举质式、判断质式、因式分解的演算法，例如 Berlekamp's Algorithm 和 Cantor-Zassenhaus Algorithm 。

列举质式：x (mod 2), x + 1 (mod 2), x² + x + 1 (mod 2), ...
判断质式：x³ + x + 1 (mod 2) is irreducible polynomial
因式分解：x² + 1 (mod 2) = x + 1 (mod 2) × x + 1 (mod 2)

馀数系统，对象是整数

5 ≡ 2 (mod 3)
4 + 5 ≡ 0 (mod 3)
4 × 5 ≡ 2 (mod 3)

先前章节皆属此类！

实际应用时，常令模数为质数，让每个数字都有乘法反元素（倒数），建立加减乘除四则运算。

馀数系统，对象是整数多项式

x³ ≡ -x - 1 (mod x³ + x + 1)
x² + (x² + 1) ≡ 2x² + 1 (mod x³ + x + 1)
x² × (x² + 1) ≡ -x (mod x³ + x + 1)

实际应用时，常令模数为质式，让每个多项式都有乘法反元素（倒数），建立加减乘除四则运算。

馀数系统，对象是馀数多项式

x³ (mod 2) ≡ x + 1 (mod 2) (mod x³ + x + 1 (mod 2))
x² (mod 2) + x² + 1 (mod 2) ≡ 1 (mod 2) (mod x³ + x + 1 (mod 2))
x² (mod 2) × x² + 1 (mod 2) ≡ x (mod 2) (mod x³ + x + 1 (mod 2))

终于来到重头戏！

实际应用时，常令模数为质式暨质数，让每个馀数多项式都有乘法反元素（倒数），建立加减乘除四则运算。简易的理解方式是：

一、多项式最多 n 项（低于 n 次），模数是质式（n 次）。

二、而且係数范围是 0 到 p-1，模数是质数 p。

标记方式是 GF(pⁿ)，另以文字说明质式为何。

GF(2³), irreducible polynomial is x³ + x + 1　（习惯省略 mod）
x³ ≡ x + 1
x² + (x² + 1) ≡ 1
x² × (x² + 1) ≡ x

“模数是质式暨质数”暨加减乘除法，数学家称做“ 有限体 ”。

馀数多项式改写成数字

馀数多项式得简化成数字：係数变位数、模数变底数。

x (mod 2)          --->  10₍₂₎ = 2₍₁₀₎
x² + 1 (mod 2)     ---> 101₍₂₎ = 5₍₁₀₎
x² + x + 1 (mod 2) ---> 111₍₂₎ = 7₍₁₀₎

将 GF(pⁿ) 如法炮制，最后便得到一个有限范围整数的运算系统，有 pⁿ种整数。不过加减乘除的结果变得非常诡异，尤其是乘除，根本毫无规律可言。由于毫无规律，所以非常适合用于制造随机排列、制造乱数、制造密码等等。

GF(2³), irreducible polynomial is x³ + x + 1 ---> 11
x³ ≡ x + 1         ---> 8 ≡ 3
x² + (x² + 1) ≡ 1  ---> 4 + 5 ≡ 1
x² × (x² + 1) ≡ x  ---> 4 × 5 ≡ 2

+ | 0  1  2  3　4  5  6  7     × | 0  1  2  3　4  5  6  7
--|-----------------------     --|-----------------------
0 | 0  1  2  3  4  5  6  7     0 | 0  0  0  0  0  0  0  0
1 | 1  0  3  2  5  4  7  6     1 | 0  1  2  3  4  5  6  7
2 | 2  3  0  1  6  7  4  5     2 | 0  2  4  6  3  1  7  5
3 | 3  2  1  0  7  6  5  4     3 | 0  3  6  5  7  4  1  2
4 | 4  5  6  7  0  1  2  3     4 | 0  4  3  7  6  2  5  1
5 | 5  4  7  6  1  0  3  2     5 | 0  5  1  4  2  7  3  6
6 | 6  7  4  5  2  3  0  1     6 | 0  6  7  1  5  3  2  4
7 | 7  6  5  4  3  2  1  0     7 | 0  7  5  2  1  6  4  3

只消调整一下质式与质数，轻鬆得到另一套诡异的运算表。

关于质数。电脑採用二进位，为了方便计算，我们习惯令质数为 2，即 GF(2ⁿ)，把馀数多项式变成二进位数字。

关于质式。馀数多项式的质式不好求。我们习惯直接使用前人留下来的表格：

http://mathworld.wolfram.com/IrreduciblePolynomial.html

乘法群

从整数推广到馀数多项式。

模数是任意的馀数多项式。取出“与模数互质的馀数多项式”。“与模数互质的馀数多项式”暨乘法除法，也是乘法群。

进一步将多项式简化为数字，可以得到超级诡异的运算系统，难以察觉规律！

原多项式（Primitive Polynomial）

从整数推广到馀数多项式。即原根！

范例：Water Jug Problem

Water Jug Problem

手边有两个容器，一个三公升、一个五公升，都没有刻度。另外身边还有一个水龙头和一个水槽，我们可以用水龙头的水装满容器，也可以把容器的水倒入水槽（有点浪费），或者把一个容器的水倒入到另一容器、装满另一容器。如何利用这两个容器量出四公升的水？

演算法（State Space Search）

请参考“ 3 Jugs Problem ”。

BFS Tree 恰好是水量变化最少的路线。可用下面的模型证明。

UVa 571

演算法（Modeling）

以三角座标系统当作模型：

http://www.cut-the-knot.org/triangle/glasses.shtml

首先建立二维座标系，只有第一象限。其中一轴为三公升的容器，范围是零到三；另外一轴为五公升的容器，范围是零到五。然后画上很多斜线：

座标代表著两容器的水量。我们描一个点来表示目前两容器的水量。一开始起点在原点，代表著两个容器都没有装水：

如果三公升的容器填满水或倒光水，点就往三公升轴的一端或另一端移动到底；五公升的容器亦同。如果两个容器互相倒水，点就往斜线方向移动到底：

至此，Water Jug Problem 变成了：由原点画线，只能画直线、横线、斜线并画到底，然后画到座标其中一个维度的数值是四的地方。

演算法（Modeling）

以馀数方程式当作模型：

http://www.matrix67.com/blog/archives/5100

两容器，体积 a 和 b；量水，体积 c。变成 ax ≡ c (mod b)。

ICPC 6501

范例：Josephus Problem

Josephus Problem

有 n 个人围成一圈，现在从第一个人开始报数，数到第 m 人时，就杀掉这第 m 人；然后从被杀的下一位继续重新报数，数到第 m 人时，就杀掉这第 m 人。如此不断数 m 人、杀此人，直到最后会剩下一个人，请问他是谁？

这个美式风格的问题似乎有点残酷。如果改成“不断数 m 个人，被点名的人就脸颊泛红，害羞的跑开了”这样应该会童真一点。

演算法（Simulation）

直接模拟“不断数 m 个人，被点名的人就脸颊泛红，害羞的跑开了”这个行为。时间複杂度为 O(nm)。

有个加速的小手段是：当要数的人数超过实际人数时，可以模一下、取馀数。

范例：Tessellation

Tessellation

http://en.wikipedia.org/wiki/Tiling_by_regular_polygons

Coordinates

UVa 209 10161 808 10182 10595 10964