P32 - 最大公约数

2026-09-07 00:00    #Haskell   #99题   #数论  

P32 - 最大公约数

Determine the greatest common divisor of two integers

官方模块：Problems.P32　核心函数：myGCD

← P31 判断素数 | P33 判断互质 →

题目描述

计算两个整数的最大公约数（GCD）。定义为能同时整除二者的最大正整数。

函数签名

1myGCD :: Integral a => a -> a -> a

实现

方法一：欧几里得算法（递归）

1myGCD :: Integral a => a -> a -> a
2myGCD a b = go (abs a) (abs b)
3  where
4    go x 0 = x
5    go x y = go y (x `mod` y)

欧几里得算法基于 gcd⁡(a,b)=gcd⁡(b,a mod b)\gcd(a,b)=\gcd(b,a\bmod b)。余数严格变小，递归必然终止。

这里把 gcd a 0 定义为 abs a，并得到 gcd 0 0 = 0，与 Prelude 的 gcd 行为一致。

方法二：欧几里得算法（尾递归）

1myGCD :: Integral a => a -> a -> a
2myGCD a b = go (abs a) (abs b)
3  where
4    go a 0 = a
5    go a b = go b (a `rem` b)

rem 和 mod 对正数的结果相同，但 rem 更快（只取余数，不保证非负）。既然我们取了绝对值，用 rem 更高效。

方法三：更相减损术

1myGCD :: Integral a => a -> a -> a
2myGCD a 0 = abs a
3myGCD 0 b = abs b
4myGCD a b
5  | abs a == abs b = abs a
6  | abs a > abs b  = myGCD (abs a - abs b) (abs b)
7  | otherwise      = myGCD (abs a) (abs b - abs a)

基于 gcd⁡(a,b)=gcd⁡(a−b,b)\gcd(a,b)=\gcd(a-b,b)，不需要取模运算。适合仅支持加减法的场景（如某些教学环境）。对大数效率不如欧几里得。

方法对比

方法核心操作迭代次数特点
递归 modmodO(log min(a,b))标准做法
尾递归 remremO(log min(a,b))rem 略快于 mod
更相减损-O(max(a,b))仅加减，教学用途

测试

1>>> myGCD 36 63
29
3>>> myGCD (-36) 63
49
5>>> myGCD 17 0
617
7>>> myGCD 0 0
80

参考