GCD / LCM 与整除结构

数学、数论与组合 · HTML

数学 / 逻辑形态

gcd(a,b)=gcd(b,a mod b)；lcm(a,b)=|a/gcd(a,b)*b|；ax+by 的可达整数恰为 gcd(a,b) 的倍数。

识别信号

• 要求最大公共单位
• 比例需化为规范形式
• 多个周期何时重合
• 整除分组或步长可达性
• 答案只依赖质因子交集

容易误判的相似信号

核心不变量

欧几里得每步保持公约数集合不变，且第二参数严格变小直到 0。

状态、转移与处理顺序

Python 骨架

def gcd(a, b):
    a, b = abs(a), abs(b)
    while b:
        a, b = b, a % b
    return a

def lcm(a, b):
    return 0 if a == 0 or b == 0 else abs(a // gcd(a,b) * b)

def normalize_ratio(x, y):
    if y == 0: return (1 if x > 0 else -1 if x < 0 else 0, 0)
    if y < 0: x, y = -x, -y
    g = gcd(x, y)
    return (x // g, y // g)

正确性思路

1. 任一公约数同时整除 a、b，也整除 a-qb=a%b。
2. 反过来整除 b 与余数的数也整除 a，所以公约数集合不变。
3. 余数绝对值下降，算法终止于 (g,0)。
4. 用 g 同除分子分母得到唯一规范比例（配合符号规则）。

复杂度

边界条件

• gcd(0,0) 常约定为 0
• 负数先取绝对值
• LCM 含 0 时为 0
• 先除后乘避免溢出
• 比例分母 0 需专门规范化

错误模式

选择与排除规则

• 共同单位、整除步长、比例归一：先想 GCD。
• 需要所有因子或指数：质因数分解。
• 周期重合用 LCM，但注意范围与溢出。
• 哈希比例时固定分母为正并处理零向量。

相关模板

原创微型例子

Recall prompts

• 欧几里得为何保持公约数集合？
• LCM 为什么先除再乘？
• 比例作为哈希键要统一哪些边界？

我的补充