Python 验证代码中的常用数学工具

2026-09-07 00:00    #Python   #算法竞赛  

Python 自带任意精度整数，标准库还提供最大公约数、整数平方根、浮点比较和有理数。写验证程序时直接使用这些工具，通常比临时重写一个版本更可靠。

任意精度整数

Python 的 int 不会像 C++ 的 long long 一样在 263−12^{63}-1 后溢出：

1x = 10 ** 100
2
3assert len(str(x)) == 101
4assert x * x == 10 ** 200

这非常适合验证组合计数、乘法和递推结果。但整数越大，运算成本仍会增加；“不会溢出”不等于“无限快”。

abs、pow 与 divmod

1assert abs(-17) == 17
2assert pow(2, 10) == 1024
3assert pow(2, 10, 1000) == 24
4assert divmod(17, 5) == (3, 2)

pow(base, exponent, mod) 直接计算模幂，不会先构造完整的巨大幂。divmod(a, b) 同时返回商和余数，相当于 (a // b, a % b)。

1for a in range(20):
2    quotient, remainder = divmod(a, 7)
3    assert a == quotient * 7 + remainder
4    assert 0 <= remainder < 7

gcd 与 lcm

1from math import gcd, lcm
2
3assert gcd(18, 24) == 6
4assert gcd(18, 24, 30) == 6
5assert lcm(6, 8) == 24
6assert lcm(6, 8, 15) == 120

多个数的最大公约数和最小公倍数可以直接传入多个参数。空参数时 gcd() 返回 0，lcm() 返回 1。

1from math import gcd, lcm
2
3assert gcd() == 0
4assert lcm() == 1

math.lcm 从 Python 3.9 开始提供。旧版本可以使用 a // gcd(a, b) * b，但要自行处理零和符号。

isqrt：精确整数平方根

math.isqrt(n) 返回 ⌊n⌋\lfloor\sqrt n\rfloor，整个过程使用整数运算：

1from math import isqrt
2
3assert isqrt(0) == 0
4assert isqrt(15) == 3
5assert isqrt(16) == 4
6assert isqrt(17) == 4

判断完全平方数：

 1from math import isqrt
 2
 3
 4def is_square(n):
 5    if n < 0:
 6        return False
 7    root = isqrt(n)
 8    return root * root == n
 9
10
11assert is_square(0)
12assert is_square(10**40)
13assert not is_square(10**40 - 1)
14assert not is_square(-1)

不要使用 int(n ** 0.5) 验证大整数。浮点数精度有限，大整数转换后可能发生舍入。

inf：初始化最优值

 1from math import inf
 2
 3best_min = inf
 4best_max = -inf
 5
 6for x in [3, -2, 7, 1]:
 7    best_min = min(best_min, x)
 8    best_max = max(best_max, x)
 9
10assert best_min == -2
11assert best_max == 7

如果“没有合法候选”是可能结果，使用 None 往往比返回 inf 更能表达无解：

1def minimum_positive(a):
2    candidates = [x for x in a if x > 0]
3    return min(candidates, default=None)
4
5
6assert minimum_positive([-3, 0, -1]) is None
7assert minimum_positive([-3, 5, 2]) == 2

浮点数不能直接依赖相等

1value = 0.1 + 0.2
2
3assert value != 0.3

验证浮点答案时使用 math.isclose：

1from math import isclose
2
3assert isclose(0.1 + 0.2, 0.3)
4assert isclose(1_000_000.0, 1_000_000.1, rel_tol=1e-6)
5assert isclose(1e-10, 0.0, abs_tol=1e-9)

判断公式近似为：

∣a−b∣≤max⁡(rel_tol⋅max⁡(∣a∣,∣b∣),abs_tol). |a-b| \leq \max(\text{rel\_tol}\cdot\max(|a|,|b|),\text{abs\_tol}).

Fraction：精确有理数

如果问题只包含整数分数，可以使用 fractions.Fraction 避免浮点误差：

1from fractions import Fraction
2
3a = Fraction(1, 3)
4b = Fraction(1, 6)
5
6assert a + b == Fraction(1, 2)
7assert a * 6 == 2

用字符串构造十进制分数可以保持字面值精确：

1from fractions import Fraction
2
3assert Fraction("0.1") + Fraction("0.2") == Fraction("0.3")

直接传入浮点数会保留这个浮点数的真实二进制值：

1from fractions import Fraction
2
3assert Fraction(0.1) != Fraction(1, 10)

Fraction 适合小规模验证，不适合无条件替换正式算法中的高性能整数表示。

用数学工具写简单验证

例如验证数组中是否存在一对数，其乘积是完全平方数：

 1from math import isqrt
 2
 3
 4def is_square(n):
 5    if n < 0:
 6        return False
 7    root = isqrt(n)
 8    return root * root == n
 9
10
11def has_square_product_pair(a):
12    return any(
13        is_square(a[i] * a[j])
14        for i in range(len(a))
15        for j in range(i + 1, len(a))
16    )
17
18
19assert has_square_product_pair([2, 8, 3])
20assert not has_square_product_pair([2, 3, 5])

这个验证版本直接检查每个点对，不需要推导质因数奇偶性。更多枚举方式见用 Python 快速编写算法暴力验证程序。

参考资料