如何高效查找包含1到n元素的数组中满足(k % a) % b = (k % b) % a的数对(a,b)

首先，我们可以通过数学推导简化原等式的条件，将问题拆分为两个部分处理，从而把时间复杂度从暴力解法的O(n²)大幅降低到O(k log k + n)（k为给定整数）。

一、等式的数学简化 #

原等式为：(k % a) % b = (k % b) % a，其中1 ≤ a < b ≤ n。

我们分两种情况分析：

情况1：当b > k时

无论a是小于b的任何值，等式都成立：

• 如果a > k：k%a = k，k%b = k，两边结果均为k；
• 如果a ≤ k：k%a < a < b，因此左边(k%a)%b = k%a；右边k%b = k，所以(k%b)%a = k%a，两边相等。

这部分数对可以直接批量处理，无需逐个判断条件。

情况2：当b ≤ k时

此时等式可简化为：k%a = (k%b) % a。进一步推导可得，该等式等价于**a能整除b * floor(k / b)**（其中floor(k/b)是k除以b的整数商）。

原因是：k%b = k - b*floor(k/b)，代入右边得(k - b*floor(k/b))%a，要等于k%a，则b*floor(k/b)必须是a的倍数。

二、优化实现示例 #

1. 列出所有符合条件的数对

def find_valid_pairs(n, k):
    valid_pairs = []
    
    # 处理b > k的所有数对
    if k < n:
        for b in range(k+1, n+1):
            for a in range(1, b):
                valid_pairs.append((a, b))
    
    # 处理b ≤ k的数对
    max_b = min(k, n)
    for b in range(2, max_b + 1):
        q = k // b
        product = b * q
        # 找出所有小于b且能整除product的a
        factors = set()
        # 枚举product的因数
        for i in range(1, int(product**0.5) + 1):
            if product % i == 0:
                if i < b:
                    factors.add(i)
                counterpart = product // i
                if counterpart < b and counterpart != i:
                    factors.add(counterpart)
        # 将符合条件的(a,b)加入结果
        for a in sorted(factors):
            valid_pairs.append((a, b))
    
    return valid_pairs

2. 仅统计符合条件的数对数量（更高效）

如果不需要列出所有数对，只需要统计数量，可以用公式快速计算b>k部分的数量，避免枚举：

def count_valid_pairs(n, k):
    count = 0
    
    # 计算b > k的数对数量
    if k < n:
        # 求和公式：sum_{b=k+1}^n (b-1) = (k + n-1) * (n - k) // 2
        count += (k + n - 1) * (n - k) // 2
    
    # 计算b ≤ k的数对数量
    max_b = min(k, n)
    for b in range(2, max_b + 1):
        q = k // b
        product = b * q
        factor_count = 0
        # 统计小于b的因数数量
        for i in range(1, int(product**0.5) + 1):
            if product % i == 0:
                if i < b:
                    factor_count += 1
                counterpart = product // i
                if counterpart != i and counterpart < b:
                    factor_count += 1
        count += factor_count
    
    return count

三、复杂度分析 #

• 处理b>k部分：如果需要列出数对，时间复杂度为O((n-k)*k)；如果仅统计数量，时间复杂度为O(1)。
• 处理b≤k部分：每个b对应的因数枚举时间为O(sqrt(product))，而product ≤k，因此总时间复杂度为O(k*sqrt(k))，远低于暴力解法的O(n²)。

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