如何高效求解康托尔有理数集第N项 适配n最高达10^18场景

核心原理 #

康托尔对角遍历法按分子与分母的和s对有理数分组，每组包含s-1个有理数：

• s=2：共1项，对应n=1
• s=3：共2项，对应n=2~3
• s=4：共3项，对应n=4~6
• ...
• s=k：共k-1项，对应n的范围为(k-2)*(k-1)/2 + 1 ~ (k-1)*k/2

常规实现的性能瓶颈在于线性遍历累加计算分组值s，当n达到1e18时需要循环约1.4e9次，完全无法满足性能要求。我们可以通过整数平方根计算在O(1)时间内定位到s，再计算组内偏移即可得到最终的分子分母。

实现步骤 #

1. 定位分组值s
   计算判别式d = 8 * n + 1，取d的整数平方根sqrt_d，初步计算s = (sqrt_d - 1) // 2，可加一步校验修正避免平方根精度误差。
2. 计算组内偏移
   offset = n - s * (s - 1) // 2
3. 按奇偶性生成有理数
   s为奇数时遍历方向为分子从大到小、分母从小到大，s为偶数时相反：

• 奇数：分子为s + 1 - offset，分母为offset
• 偶数：分子为offset，分母为s + 1 - offset

代码示例 #

import math

def nth_rational(n: int) -> tuple[int, int]:
    if n <= 0:
        raise ValueError("n必须为正整数")
    d = 8 * n + 1
    sqrt_d = math.isqrt(d)
    s = (sqrt_d - 1) // 2
    # 精度校验修正
    if s * (s + 1) // 2 < n:
        s += 1
    offset = n - s * (s - 1) // 2
    if s % 2 == 1:
        return (s + 1 - offset, offset)
    else:
        return (offset, s + 1 - offset)

性能说明 #

• 时间复杂度O(1)：所有运算均为常数次整数操作，即使n为1e18也能在纳秒级返回结果
• 空间复杂度O(1)：无额外空间开销
• 如需匹配其他遍历顺序，仅需交换奇偶分支的分子分母返回值即可

内容的提问来源于stack exchange，提问作者WallRunner