P43 - 高斯整数整除

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

P43 - 高斯整数整除

Determine whether a Gaussian integer divides another

官方模块：Problems.P43　核心函数：gaussianDividesBy

← P42 模乘逆元 | P44 朴素判定高斯素数 →

题目描述

判断一个高斯整数是否整除另一个高斯整数。高斯整数形如 a+bia+bi，判别 x/yx/y 的实部与虚部是否都是整数。

函数签名

1gaussianDividesBy :: Complex Integer -> Complex Integer -> Bool

Complex Integer 没有普通复数除法；直接检查两个分子能否被范数整除，恰好避免了浮点误差。

实现

方法一：分母实数化

 1import Data.Complex (Complex((:+)))
 2
 3gaussianDividesBy :: Complex Integer -> Complex Integer -> Bool
 4gaussianDividesBy _ (0 :+ 0) = False
 5gaussianDividesBy (a :+ b) (c :+ d) =
 6  realNumerator `mod` denominator == 0
 7  && imagNumerator `mod` denominator == 0
 8  where
 9    realNumerator = a * c + b * d
10    imagNumerator = b * c - a * d
11    denominator   = c * c + d * d

将分母实数化 a+bic+di=(ac+bd)+(bc−ad)ic2+d2\frac{a+bi}{c+di} = \frac{(ac+bd)+(bc-ad)i}{c^2+d^2}，检查两个分子能否被范数整除。

方法二：枚举高斯整数商

 1import Data.Complex (Complex((:+)))
 2
 3gaussianDividesBySearch :: Complex Integer -> Complex Integer -> Bool
 4gaussianDividesBySearch _ (0 :+ 0) = False
 5gaussianDividesBySearch target divisor =
 6  any ((== target) . multiply divisor) candidates
 7  where
 8    targetNorm = norm target
 9    candidates = [r :+ i | r <- [-targetNorm..targetNorm]
10                           , i <- [-targetNorm..targetNorm]]
11
12    norm (a :+ b) = a * a + b * b
13
14    multiply (a :+ b) (c :+ d) =
15      (a * c - b * d) :+ (a * d + b * c)

若 divisor 整除 target，就存在高斯整数 qq 使 divisor * q == target。商的范数不会超过被除数的范数，所以在这个有限范围内枚举实部和虚部即可。这个版本很慢，但它直接按照“存在整数商”的定义求解，适合验证方法一。

方法对比

方法特点
分母实数化O(1) 代数判定，推荐
枚举高斯整数商定义直译，适合小数值交叉验证

测试

 1>>> (10 :+ 0) `gaussianDividesBy` (2 :+ 0)
 2True
 3>>> (10 :+ 0) `gaussianDividesBy` (0 :+ 2)
 4True
 5>>> (5 :+ 2) `gaussianDividesBy` (2 :+ (-1))
 6False
 7>>> gaussianDividesBySearch (10 :+ 0) (0 :+ 2)
 8True
 9>>> gaussianDividesBy (0 :+ 0) (0 :+ 0)
10False

参考