前言

大家好，这里是 Charming讲Python编码小技巧 系列专栏。每天分享一个 30-seconds-of-python 仓库中的神级写法，助你告别"屎山"代码，写出让人眼前一亮的 Pythonic 风格！

小技巧内容描述

最大公约数（Greatest Common Divisor，GCD），这是数学中最基础也是最重要的概念之一！在算法、密码学、分数运算中无处不在。

还在手写辗转相除法？今天教你一个超优雅的实现方式！

from functools import reduce
from math import gcd as _gcd

def gcd(numbers):
    return reduce(_gcd, numbers)

就这么简单！让我来详细解释一下为什么这么写。

为什么这么用？

核心原理：reduce函数的威力

这个技巧的核心在于使用Python的reduce函数对列表中的所有元素进行累积计算：

1. from math import gcd as _gcd - 导入Python内置的gcd函数
2. reduce(_gcd, numbers) - 对列表中的所有数字依次计算gcd

reduce的工作原理：

• gcd([a, b, c]) 等价于 gcd(gcd(a, b), c)
• gcd([8, 36, 28]) 等价于 gcd(gcd(8, 36), 28) = gcd(4, 28) = 4

举个栗子

# 基础示例
print(gcd([8, 36]))        # 4
print(gcd([8, 36, 28]))    # 4
print(gcd([12, 18, 24]))   # 6
print(gcd([15, 25, 35]))   # 5

# 两个数的情况
print(gcd([12, 8]))        # 4
print(gcd([17, 23]))       # 1 (互质)

# 多个数的情况
print(gcd([2, 4, 8, 16]))  # 2
print(gcd([6, 12, 18, 24])) # 6

更多实用场景

场景一：分数化简

def simplify_fraction(numerator, denominator):
    """化简分数"""
    from math import gcd
    divisor = gcd(numerator, denominator)
    return numerator // divisor, denominator // divisor

# 测试
print(simplify_fraction(8, 12))    # (2, 3)
print(simplify_fraction(15, 25))   # (3, 5)
print(simplify_fraction(100, 75))  # (4, 3)
print(simplify_fraction(17, 23))   # (17, 23) (已是最简)

# 格式化输出
def format_fraction(n, d):
    num, den = simplify_fraction(n, d)
    if den == 1:
        return str(num)
    return f"{num}/{den}"

print(format_fraction(8, 12))   # "2/3"
print(format_fraction(4, 2))    # "2"

场景二：最小公倍数（LCM）

from math import gcd

def lcm(a, b):
    """计算两个数的最小公倍数"""
    return a * b // gcd(a, b)

def lcm_multiple(numbers):
    """计算多个数的最小公倍数"""
    from functools import reduce
    return reduce(lcm, numbers)

# 测试
print(lcm(4, 6))           # 12
print(lcm(12, 15))         # 60
print(lcm_multiple([4, 6, 8]))   # 24
print(lcm_multiple([2, 3, 5]))   # 30

# 实际应用：计算周期
print("\n📅 周期计算：")
print(f"每3天和每4天的任务，每{lcm(3, 4)}天会同时执行")  # 12天
print(f"每6小时和每8小时的检查，每{lcm(6, 8)}小时同时进行")  # 24小时

场景三：判断是否互质

from math import gcd

def are_coprime(numbers):
    """判断一组数是否互质"""
    return gcd(numbers) == 1

# 测试
print(are_coprime([17, 23]))          # True
print(are_coprime([8, 15]))           # True
print(are_coprime([12, 18]))          # False
print(are_coprime([2, 3, 5]))         # True
print(are_coprime([4, 6, 8]))         # False

# 密码学应用：RSA算法需要选择互质的数
print("\n🔐 密码学应用：")
print(f"选择e=65537，phi=3233，是否互质: {are_coprime([65537, 3233])}")

场景四：求解线性方程组

def solve_linear_diophantine(a, b, c):
    """求解线性Diophantine方程 ax + by = c"""
    from math import gcd

    d = gcd(a, b)

    if c % d != 0:
        return None  # 无解

    # 简化方程
    a_simplified = a // d
    b_simplified = b // d
    c_simplified = c // d

    # 找到一个特解（这里使用扩展欧几里得算法的简化版本）
    # 注意：完整实现需要扩展欧几里得算法
    return f"方程有解，gcd({a}, {b}) = {d}，且 {c} 能被 {d} 整除"

# 测试
print(solve_linear_diophantine(3, 5, 8))   # 有解
print(solve_linear_diophantine(2, 4, 7))   # 无解

场景五：分数运算

from math import gcd

class Fraction:
    """分数类"""
    def __init__(self, numerator, denominator):
        if denominator == 0:
            raise ValueError("分母不能为0")
        self.numerator = numerator
        self.denominator = denominator
        self.simplify()

    def simplify(self):
        """化简分数"""
        d = gcd(abs(self.numerator), abs(self.denominator))
        self.numerator //= d
        self.denominator //= d
        # 确保分母为正
        if self.denominator < 0:
            self.numerator *= -1
            self.denominator *= -1

    def __add__(self, other):
        num = self.numerator * other.denominator + other.numerator * self.denominator
        den = self.denominator * other.denominator
        return Fraction(num, den)

    def __sub__(self, other):
        num = self.numerator * other.denominator - other.numerator * self.denominator
        den = self.denominator * other.denominator
        return Fraction(num, den)

    def __mul__(self, other):
        num = self.numerator * other.numerator
        den = self.denominator * other.denominator
        return Fraction(num, den)

    def __truediv__(self, other):
        num = self.numerator * other.denominator
        den = self.denominator * other.numerator
        return Fraction(num, den)

    def __str__(self):
        if self.denominator == 1:
            return str(self.numerator)
        return f"{self.numerator}/{self.denominator}"

# 测试
print("➕ 分数加法：")
print(f"1/2 + 1/3 = {Fraction(1, 2) + Fraction(1, 3)}")  # 5/6
print(f"2/3 + 3/4 = {Fraction(2, 3) + Fraction(3, 4)}")  # 17/12

print("\n➖ 分数减法：")
print(f"3/4 - 1/2 = {Fraction(3, 4) - Fraction(1, 2)}")  # 1/4

print("\n✖️ 分数乘法：")
print(f"2/3 × 3/4 = {Fraction(2, 3) * Fraction(3, 4)}")  # 1/2

print("\n➗ 分数除法：")
print(f"2/3 ÷ 4/5 = {Fraction(2, 3) / Fraction(4, 5)}")  # 5/6

场景六：最大公约数的实际应用

from math import gcd

def tile_floor(length, width, tile_size):
    """计算用给定大小的瓷砖铺满地面需要多少块"""
    # 计算地面和瓷砖的最大公约数
    # 实际上我们需要计算需要多少块瓷砖
    tiles_length = (length + tile_size - 1) // tile_size
    tiles_width = (width + tile_size - 1) // tile_size
    return tiles_length * tiles_width

def max_square_tile(length, width):
    """计算能铺满矩形地面的最大正方形瓷砖尺寸"""
    return gcd(length, width)

# 测试
print("🏠 铺砖问题：")
floor_length = 24
floor_width = 18
max_tile = max_square_tile(floor_length, floor_width)
print(f"地面尺寸: {floor_length}×{floor_width}")
print(f"最大正方形瓷砖: {max_tile}×{max_tile}")
print(f"需要瓷砖数量: {(floor_length // max_tile) * (floor_width // max_tile)}块")

对比其他实现方式

方法1：欧几里得算法（经典）

def gcd_euclidean(a, b):
    """欧几里得算法"""
    while b:
        a, b = b, a % b
    return a

print(gcd_euclidean(8, 36))  # 4

方法2：递归实现

def gcd_recursive(a, b):
    """递归实现"""
    return a if b == 0 else gcd_recursive(b, a % b)

print(gcd_recursive(8, 36))  # 4

方法3：扩展欧几里得算法

def extended_gcd(a, b):
    """扩展欧几里得算法，返回gcd和系数"""
    if b == 0:
        return a, 1, 0
    else:
        g, x, y = extended_gcd(b, a % b)
        return g, y, x - (a // b) * y

# 测试
g, x, y = extended_gcd(8, 36)
print(f"gcd(8, 36) = {g}")
print(f"8 × {x} + 36 × {y} = {g}")

我们的版本（推荐）

from functools import reduce
from math import gcd as _gcd

def gcd(numbers):
    return reduce(_gcd, numbers)

对比总结：

• 欧几里得算法：经典但只能处理两个数
• 递归实现：优雅但可能栈溢出
• 扩展欧几里得：功能强大但复杂
• 我们的版本：简洁高效，支持多个数

性能对比

import time
from math import gcd as _gcd

# 测试数据
test_cases = [
    (8, 36),
    (12, 18),
    (1000000, 1000001),
    (123456789, 987654321)
]

# 测试各种方法
for a, b in test_cases:
    # 方法1：内置gcd
    start = time.time()
    for _ in range(100000):
        _gcd(a, b)
    print(f"gcd({a}, {b}) = {_gcd(a, b)}, 内置方法: {time.time() - start:.4f}秒")

    # 方法2：欧几里得算法
    start = time.time()
    for _ in range(100000):
        gcd_euclidean(a, b)
    print(f"gcd({a}, {b}) = {gcd_euclidean(a, b)}, 欧几里得: {time.time() - start:.4f}秒")

    print()

总结

最大公约数这个技巧之所以如此重要，是因为：

1. 数学基础：是数论中最基础的概念之一
2. 应用广泛：分数运算、密码学、算法设计
3. 代码简洁：使用reduce函数一行搞定
4. 性能优秀：Python内置实现，效率很高
5. 面试高频：是算法面试的经典考题

GCD小知识

1. 欧几里得算法：公元前300年就提出，至今仍在使用
2. 时间复杂度：O(log(min(a, b)))，非常高效
3. 互质数：gcd为1的两个数称为互质
4. RSA算法：现代密码学的基础，依赖gcd和互质数

面试技巧

在面试中，如果这道题是面试官问的，可以这样回答：

def gcd_interview(numbers):
    """
    计算一组数的最大公约数

    思路：
    1. 使用Python内置的math.gcd函数计算两个数的gcd
    2. 使用reduce函数对列表中的所有数依次计算gcd

    时间复杂度：O(n × log(max(numbers)))
    空间复杂度：O(1)
    """
    from functools import reduce
    from math import gcd
    return reduce(gcd, numbers)

---

今日小技巧： gcd() - 一行代码计算最大公约数

适用场景： 分数运算、密码学、算法设计、数学问题求解

点赞收藏，每天学一个Python神技巧！