Question

使用乘法，凑得给定数字

给你一个数，例如 12 好了，要拿哪些数字相乘，才会得到 12 呢？例如 1×12=12、2×6=12、3×4=12 等等。

Divisor（Factor）

一个数字的“因数”，是可以用来凑得此数字的所有数字。

凑合与分解，一体两面。一个数字的“因数”，就是此数字进行分解，可能出现的所有数字。

0: 0       5: 1 5       10: 1 2 5 10
1: 1       6: 1 2 3 6   11: 1 11
2: 1 2     7: 1 7       12: 1 2 3 4 6 12
3: 1 3     8: 1 2 4 8   13: 1 13
4: 1 2 4   9: 1 3 9     14: 1 2 7 14

Enumerate Divisors

演算法

试误法。由 1 开始尝试每种数字作为因数。

Greatest Common Divisor

Greatest Common Divisor

多个数字，大家都有的因数们，当中最大的一个，叫做“最大公因数”。

0: 0 1 2 ...   5: 1 5       10: 1 2 5 10
1: 1           6: 1 2 3 6   11: 1 11
2: 1 2         7: 1 7       12: 1 2 3 4 6 12
3: 1 3         8: 1 2 4 8   13: 1 13
4: 1 2 4       9: 1 3 9     14: 1 2 7 14

gcd(8, 8, 8, 8, 8) = 8
gcd(6, 9, 12) = 3
gcd(2, 3, 5, 7, 11) = 1
gcd(1, 8) = 1
gcd(0, 8) = 8

试误法。由大到小穷举每个数字作为最大公因数。

多个数字的最大公因数可以使用递归法计算：任取几个数字，换成它们的最大公因数。

把最大公因数想成是万丈高楼平地起的砖块们就简单多了。

可以直接使用 GNU Extension 的__gcd()。

Least Common Multiple

多个数字，大家都有的倍数们，当中最小的一个，叫做“最小公倍数”。

公式：gcd(a,b) * lcm(a,b) = a * b。

Greatest Common Divisor: Euclidean Algorithm

Euclidean Algorithm（Euclid's Algorithm）

几何学之父欧几里德所发明的“辗转相除法”，用来求两个数的最大公因数。几何学之父原来跟数论也扯得上关係。

由于两个数必定是由最大公因数的整数倍所组合而成，故其差值也必定由最大公因数的整数倍所组合而成，不管两数如何辗转相减、辗转求馀数，其得到的值都会是最大公因数的倍数。把最大公因数想成是万丈高楼平地起的砖块们就简单多了。

求出了差值后，原问题便缩小成了跟原问题类似的问题。也就是说，辗转相除法採取了 Divide and Conquer 的策略。

时间複杂度

时间複杂度是 O(logB)，其中 B 是两数中较小的那个数。时间複杂度可用 Fibonacci Sequence 算得，详情可参考离散数学的书籍。

程式码

迴圈版本。

另一种奇怪的迴圈版本。仅供参考。

递迴版本。

写的很简略。自己实作时，敬请注意参数的数值范围。

UVa 10193 10407

Greatest Common Divisor: Extended Euclidean Algorithm

Extended Euclidean Algorithm

辗转相除法的扩充版本。除了可以找出两数的最大公因数，还可以顺便找出此两数各乘上多少整数倍率后相加可得到最大公因数（倍率可以是负数或零），并且让两个整数倍率的绝对值都最小。

以数学符号来表示，这个演算法可以找出 a b 两数的最大公因数 d，还可以顺便找出满足 a×i + b×j = d 的两个整数倍率 i j，并且让|i|与|j|最小。

採用递推法。首先分别複制 a b 到 c d 上面，以 c d 两数来辗转相除。然后设计另外两个整数倍率 i' j'，令每次辗转相除时都保持 a×i' + b×j' = c 且 a×i + b×j = d。根据辗转相除的式子 r = c - q×d，推得 r = c - q×d = (a×i' + b×j') - q × (a×i + b×j) = a × (i'-q×i) + b × (j'-q×j)。如此一来，在辗转相除时，就知道 i j 两数如何随著 r 变动了。

http://math.stackexchange.com/questions/670405/

採用递归法。以 Divide and Conquer 的 Combine 阶段来计算 i j。当问题分割至最小，此时可以明确的、轻鬆的算出 i j 的值。每次合併问题，就重新调整 i j，保持|i|与|j|最小。

UVa 10104

延伸阅读：Linear Diophantine Equation

已知 a b c，求出 x y，使得 a×x + b×y = c。

一、辗转相除法：
　　求得 a×i + b×j = d，其中 d = gcd(a, b)。
二、得到其中一组解：
　甲、检查 d 的倍数是不是 c。
　　回、如果是：
　　　　整个式子乘上 c÷d，让 d 变成 c，
　　　　式子变成 a×i×c÷d + b×j×c÷d = c -①
　　　　显然 (x,y) = (i×c÷d, j×c÷d) 就是其中一组解！
　　回、如果不是：
　　　　无解！
三、得到所有解：
　甲、首先制造一个式子 a×(?) + b×(?) = 0 目的是要等于零。
　　　直觉就能想到 a×b + b×(-a) = 0
　　　更进一步想到 a×b÷d + b×(-a)÷d = 0 -②
　乙、式子①加上式子②的各种倍率，也就是①+②×k：
　　　a×(i×c÷d + k×b÷d) + b×(j×c÷d - k×a÷d) = 0，其中 k 是整数。
　　　显然 (x,y) = (i×c÷d + k×b÷d, j×c÷d - k×a÷d) 就是所有解！
四、得到所有非负整数解（假设 a b 为正数）：
　甲、也就是说，(i×c÷d + k×b÷d) 与(j×c÷d - k×a÷d) 必须是非负整数。
　　　(i×c÷d + k×b÷d) ≥ 0  ⇒  k ≥ -i×c÷b
　　　(j×c÷d - k×a÷d) ≥ 0  ⇒  k ≤ +j×c÷a
　　　 -i×c÷b  ≤ k ≤  +j×c÷a
　　　⌈-i×c÷b⌉ ≤ k ≤ ⌊+j×c÷a⌋
　　　因为 k 是整数，所以取天花板和地板。进而得到所有非负整数解。

UVa 10090 10548 10413 11312

延伸阅读：Pell Equation

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

金斌《欧几里得算法的应用》。

Greatest Common Divisor: Binary GCD Algorithm

Binary GCD Algorithm

在九章数学裡称作“更相减损术”，二进位数字的最大公因数计算方法。

如果 a b 有一个是零     -> gcd(a, b) = a 和 b 当中不是零的那ㄧ个数
如果 a b 都是偶数       -> gcd(a, b) = gcd(a/2, b/2) × 2;
如果 a 是偶数  b 是奇数 -> gcd(a, b) = gcd(a/2, b)
如果 a 是奇数  b 是偶数 -> gcd(a, b) = gcd(a, b/2)
如果 a b 都是奇数       -> gcd(a, b) = gcd(a 和 b 比较小那个, a 和 b 的差);

电脑裡的数字都是用二进位储存的──要乘以二，就把数字的每个 bit 都左移一个 bit；要除以二，就把数字的每个 bit 都右移一个 bit（别忘记补零）。位移运算比除法运算、模数运算还要快，于是便开发了以提取因数二来计算最大公因数的方法。

归纳要点：甲、不断提取共同的因数，都只提取二；乙、二与奇数互质，不会影响最大公因数，故可除去二；丙、若无因数二则相减，相减后仍是最大公因数的倍数。

时间複杂度是 O((logAB)^2)，AB 为 a b 两数的乘积。【待补证明】【待补速度讨论】

程式码

这裡提供几支程式码供大家参考。

Divisibility

整除性

判断是否能整除一个数字。

换句话说。判断一个数字是否是因数，是否可以用于分解。

2: 末位数整除 2（个位数是偶数）
3: 所有位数加起来，不断递迴
4: 末两位数整除 4
5: 末位数整除 5
6: 用 2 和 3 来判定

原理是 Scaling Method，数字拆开成各种数量级，分别试除、取馀数、相加。

UVa 10212 10929 11879 10211 10127 10275 ICPC 4119

位数判断

http://www.stat.ualberta.ca/people/schmu/preprints/factorial.pdf

UVa 1185 10061 701 10212 12689

位数循环

UVa 10162

Partition（Under Construction!）

使用加法，凑得给定数字

大家都是从数数开始学数学的，1+1=2，想必大家都会。

问题来了！给你一个数，例如 5 好了，要拿哪些数字相加，才会得到 5 呢？例如 2+3=5、1+1+1+1+1=5 等等。

最简单的方式就是慢慢地列出来，可以发现有许多种相加方式，一时列举不完。如果你对演算法相当熟悉，你一定马上联想到 Backtracking、Dynamic Programming 等等方法，以及 Integer Partition、Knapsack Problem 等等问题。

Partition（Composition）

一个数字的“分割”，是可以用来凑得此数字的所有数字。

凑合与分解，一体两面。一个数字的“分割”，就是此数字进行分解，可能出现的所有数字。

Young Tableau / Ferrers Diagram

不重覆组合、生成函数

Polygonal Number

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

https://en.wikipedia.org/wiki/Domino_tiling