我是如何用「最大公約數(shù)」秒殺算法題的

關(guān)于最大公約數(shù)有專門的研究。而在 LeetCode 中雖然沒(méi)有直接讓你求解最大公約數(shù)的題目。但是卻有一些間接需要你求解最大公約數(shù)的題目。

比如：

• 914. 卡牌分組^[1]
• 365. 水壺問(wèn)題^[2]
• 1071. 字符串的最大公因子^[3]

因此如何求解最大公約數(shù)就顯得重要了。

如何求最大公約數(shù)？

定義法

def GCD(a: int, b: int) -> int:
    smaller = min(a, b)
    while smaller:
        if a % smaller == 0 and b % smaller == 0:
            return smaller
        smaller -= 1

「復(fù)雜度分析」

• 時(shí)間復(fù)雜度：最好的情況是執(zhí)行一次循環(huán)體，最壞的情況是循環(huán)到 smaller 為 1，因此總的時(shí)間復(fù)雜度為 ，其中 N 為 a 和 b 中較小的數(shù)。
• 空間復(fù)雜度：。

輾轉(zhuǎn)相除法

如果我們需要計(jì)算 a 和 b 的最大公約數(shù)，運(yùn)用輾轉(zhuǎn)相除法的話。首先，我們先計(jì)算出 a 除以 b 的余數(shù) c，把問(wèn)題轉(zhuǎn)化成求出 b 和 c 的最大公約數(shù)；然后計(jì)算出 b 除以 c 的余數(shù) d，把問(wèn)題轉(zhuǎn)化成求出 c 和 d 的最大公約數(shù)；再然后計(jì)算出 c 除以 d 的余數(shù) e，把問(wèn)題轉(zhuǎn)化成求出 d 和 e 的最大公約數(shù)。..... 以此類推，逐漸把兩個(gè)較大整數(shù)之間的運(yùn)算轉(zhuǎn)化為兩個(gè)較小整數(shù)之間的運(yùn)算，直到兩個(gè)數(shù)可以整除為止。

def GCD(a: int, b: int) -> int:
    return a if b == 0 else GCD(b, a % b)

「復(fù)雜度分析」

• 時(shí)間復(fù)雜度：
• 空間復(fù)雜度：空間復(fù)雜度取決于遞歸的深度，因此空間復(fù)雜度為

更相減損術(shù)

輾轉(zhuǎn)相除法如果 a 和 b 都很大的時(shí)候，a % b 性能會(huì)較低。在中國(guó)，《九章算術(shù)》中提到了一種類似輾轉(zhuǎn)相減法的 更相減損術(shù)^[4]。它的原理是：兩個(gè)正整數(shù) a 和 b（a>b），它們的最大公約數(shù)等于 a-b 的差值 c 和較小數(shù) b 的最大公約數(shù)。。

def GCD(a: int, b: int) -> int:
    if a == b:
        return a
    if a < b:
        return GCD(b - a, a)
    return GCD(a - b, b)

上面的代碼會(huì)報(bào)棧溢出。原因在于如果 a 和 b 相差比較大的話，遞歸次數(shù)會(huì)明顯增加，要比輾轉(zhuǎn)相除法遞歸深度增加很多，最壞時(shí)間復(fù)雜度為 O(max(a, b)))。這個(gè)時(shí)候我們可以將輾轉(zhuǎn)相除法和更相減損術(shù)做一個(gè)結(jié)合，從而在各種情況都可以獲得較好的性能。

形象化解釋

下面我們對(duì)上面的過(guò)程進(jìn)行一個(gè)表形象地講解，實(shí)際上這也是教材里面的講解方式，我只是照搬過(guò)來(lái)，增加一下自己的理解罷了。我們來(lái)通過(guò)一個(gè)例子來(lái)講解：

假如我們有一塊 1680 米 * 640 米 的土地，我們希望講起分成若干正方形的土地，且我們想讓正方形土地的邊長(zhǎng)盡可能大，我們應(yīng)該如何設(shè)計(jì)算法呢？

實(shí)際上這正是一個(gè)最大公約數(shù)的應(yīng)用場(chǎng)景，我們的目標(biāo)就是求解 1680 和 640 的最大公約數(shù)。

將 1680 米 * 640 米 的土地分割，相當(dāng)于對(duì)將 400 米 * 640 米 的土地進(jìn)行分割。為什么呢？假如 400 米 * 640 米分割的正方形邊長(zhǎng)為 x，那么有 640 % x == 0，那么肯定也滿足剩下的兩塊 640 米 * 640 米的。

我們不斷進(jìn)行上面的分割：

直到邊長(zhǎng)為 80，沒(méi)有必要進(jìn)行下去了。

實(shí)例解析

題目描述

給你三個(gè)數(shù)字 a，b，c，你需要找到第 n 個(gè)（n 從 0 開始）有序序列的值，這個(gè)有序序列是由 a，b，c 的整數(shù)倍構(gòu)成的。

比如：
n = 8
a = 2
b = 5
c = 7

由于 2，5，7 構(gòu)成的整數(shù)倍構(gòu)成的有序序列為 [1, 2, 4, 5, 6, 7, 8, 10, 12, ...]，因此我們需要返回 12。

注意：我們約定，有序序列的第一個(gè)永遠(yuǎn)是 1。

思路

大家可以通過(guò) 這個(gè)網(wǎng)站^[5] 在線驗(yàn)證。

一個(gè)簡(jiǎn)單的思路是使用堆來(lái)做，唯一需要注意的是去重，我們可以使用一個(gè)哈希表來(lái)記錄出現(xiàn)過(guò)的數(shù)字，以達(dá)到去重的目的。

代碼：

ss Solution:
    def solve(self, n, a, b, c):
        seen = set()
        h = [(a, a, 1), (b, b, 1), (c, c, 1)]
        heapq.heapify(h)

        while True:
            cur, base, times = heapq.heappop(h)
            if cur not in seen:
                n -= 1
                seen.add(cur)
            if n == 0:
                return cur
            heapq.heappush(h, (base * (times + 1), base, times + 1))

對(duì)于此解法不理解的可先看下我之前寫的 幾乎刷完了力扣所有的堆題，我發(fā)現(xiàn)了這些東西。。。（第二彈） ^[6]

然而這種做法時(shí)間復(fù)雜度太高，有沒(méi)有更好的做法呢？

實(shí)際上，我們可對(duì)搜索空間進(jìn)行二分。首先思考一個(gè)問(wèn)題，如果給定一個(gè)數(shù)字 x，那么有序序列中小于等于 x 的值有幾個(gè)。

答案是 x // a + x // b + x // c 嗎？

?

// 是地板除

?

可惜不是的。比如 a = 2, b = 4, n = 4，答案顯然不是 4 // 2 + 4 // 4 = 3，而是 2。這里出錯(cuò)的原因在于 4 被計(jì)算了兩次，一次是 ，另一次是 。

為了解決這個(gè)問(wèn)題，我們可以通過(guò)集合論的知識(shí)。

一點(diǎn)點(diǎn)集合知識(shí)：

• 如果把有序序列中小于等于 x 的可以被 x 整除，且是 a 的倍數(shù)的值構(gòu)成的集合為 SA，集合大小為 A
• 如果把有序序列中小于等于 x 的可以被 x 整除，且是 b 的倍數(shù)的值構(gòu)成的集合為 SB，集合大小為 B
• 如果把有序序列中小于等于 x 的可以被 x 整除，且是 c 的倍數(shù)的值構(gòu)成的集合為 SC，集合大小為 C

那么最終的答案就是 SA ，SB，SC 構(gòu)成的大的集合（需要去重）的中的數(shù)字的個(gè)數(shù)，也就是：

問(wèn)題轉(zhuǎn)化為 A 和 B 集合交集的個(gè)數(shù)如何求？

?

A 和 B，B 和 C， A 和 C ，甚至是 A，B，C 的交集求法都是一樣的。

?

實(shí)際上， SA 和 SB 的交集個(gè)數(shù)就是 x // lcm(A, B)，其中 lcm 為 A 和 B 的最小公倍數(shù)。而最小公倍數(shù)則可以通過(guò)最大公約數(shù)計(jì)算出來(lái)：

def lcm(x, y):
    return x * y // gcd(x, y)

接下來(lái)就是二分套路了，二分部分看不懂的建議看下我的二分專題^[7]。

代碼（Python3）

class Solution:
    def solve(self, n, a, b, c):
        def gcd(x, y):
            if y == 0:
                return x
            return gcd(y, x % y)

        def lcm(x, y):
            return x * y // gcd(x, y)

        def possible(mid):
            return (mid // a + mid // b + mid // c - mid // lcm(a, b) - mid // lcm(b, c) - mid // lcm(a, c) + mid // lcm(a, lcm(b, c))) >= n

        l, r = 1, n * max(a, b, c)
        while l <= r:
            mid = (l + r) // 2
            if possible(mid):
                r = mid - 1
            else:
                l = mid + 1
        return l

「復(fù)雜度分析」

• 時(shí)間復(fù)雜度：。
• 空間復(fù)雜度：gcd 和 lcm 的遞歸樹深度，基本可忽略不計(jì)。

總結(jié)

通過(guò)這篇文章，我們不僅明白了最大公約數(shù)的「概念以及求法」。也形象化地感知到了最大公約數(shù)計(jì)算的「原理」。最大公約數(shù)和最小公倍數(shù)是兩個(gè)相似的概念， 關(guān)于最大公約數(shù)和最小公倍數(shù)的題目在力扣中不算少，大家可以通過(guò)「數(shù)學(xué)標(biāo)簽」找到這些題。更多關(guān)于算法中的數(shù)學(xué)知識(shí)，可以參考這篇文章刷算法題必備的數(shù)學(xué)考點(diǎn)匯總 ^[8]

?

這篇文章的第二篇也馬上要發(fā)布了。

?

Reference