Divisor

使用乘法,湊得給定數字

給你一個數,例如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開始嘗試每種數字作為因數。

因數擁有對稱性。窮舉至一半就夠了。所謂的一半,是指乘法分解的一半:開根號。

時間複雜度是O(sqrt(n))。然而前提是:不管n多大,每次除法都是O(1)。

演算法

遞歸法。質因數分解,然後嘗試所有可能的次方組合。

用紙筆計算十分簡單,寫程式計算十分困難。

時間複雜度是O(A+B),A是因數數量、B是小於等於sqrt(n)的最大因數。最差仍是O(sqrt(n))。

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