algorithm - 具有给定总和和乘积的对数

Question

我有一个数组 A连同 3 个变量 k , x和 y .我必须找到无序对的数量 (i,j)这样两个元素的总和 mod k等于 x和相同的两个元素的乘积 mod k等于y .对不必是不同的。换句话说，(i,j) 的数量这样

(A[i]+A[j])%k == x和 (A[i]*A[j])%k == y其中 0 <= i < j < size of A .

例如，设A={1,2,3,2,1} , k=2 , x=1 , y=0 .那么答案是 6，因为对是:(1,2) , (1,2) , (2,3) , (2,1) , (3,2) , 和 (2,1) .

我使用了蛮力方法，但显然这是 Not Acceptable 。

Answer 1

模运算有以下两个规则:

((a mod k) * (b mod k)) mod k = (a * b) mod k
((a mod k) + (b mod k)) mod k = (a + b) mod k

因此我们可以使用 separate chaining 将所有值排序到哈希表中和 k桶。

加法

查找m < k ，这样对于给定的 n < k : (n + m) mod k = x .这个问题只有一个解决方案:

• 如果n < x : m < x必须持有。因此 m = x - n
• 如果n == x : m = 0
• 如果n > x : 我们需要找到 m这样 n + m = x + k .因此 m = x + k - n

这样，我们可以很容易地为每个值列表确定相应的值，这样对于任何对 (a, b)两个列表的叉积 (a + b) mod k = x持有。

乘法

乘法有点棘手。幸运的是，我们已经得到了加法的匹配同余类(见上文)，它也必须是乘法的匹配同余类，因为两个约束都需要成立。要验证给定的同余类匹配，我们只需要检查 (n * m) mod k = y (n 和 m 定义如上)。如果这个表达式成立，我们就可以构建对，否则不存在匹配的元素。

实现

这将是上述示例的工作 python 代码:

def modmuladd(ls, x, y, k):
    result = []

    # create tuples of indices and values
    indices = zip(ls, range(0, len(ls)))

    # split up into congruence classes
    congruence_cls = [[] for i in range(0, k)]
    for p in indices:
        congruence_cls[p[0] % k].append(p)

    for n in range(0, k):
        # congruence class to match addition
        if n < x:
            m = x - n
        elif n == x:
            m = 0
        else:
            m = x + k - n

        # check if congruence class matches for multiplication
        if (n * m) % k != y or len(congruence_cls[m]) == 0:
            continue    # no matching congruence class

        # add matching tuple to result
        result += [(a, b) for a in congruence_cls[n] for b in congruence_cls[m] if a[1] <= b[1]]
        result += [(a, b) for a in congruence_cls[m] for b in congruence_cls[n] if a[1] <= b[1]]

    # sort result such according to indices of first and second element, remove duplicates
    sorted_res = sorted(sorted(set(result), key=lambda p: p[1][1]), key=lambda p: p[0][1])

    # remove indices from result-set
    return [(p[0][0], p[1][0]) for p in sorted_res]

请注意，仅需要排序和消除重复项，因为此代码专注于同余类的使用，而不是完美优化。可以很容易地调整此示例以提供排序，而无需通过较小的修改进行排序。

试运行

print(modmuladd([1, 2, 3, 2, 1], 1, 0, 2))

输出:

[(1, 2), (1, 2), (2, 3), (2, 1), (3, 2), (2, 1)]

编辑:

该算法的最坏情况复杂度仍然是 O(n^2) ，由于构建所有可能的大小列表对 n是O(n^2) .但是，使用此算法可以将匹配对的搜索减少到O(k)。与 O(n)预处理。因此可以在 O(n) 中计算结果对用这种方法。假设数字在同余类上平均分布，该算法可以构建属于 O(n^2/k^2) 中解决方案集的所有对。 .

编辑 2:
一个只计算的实现会像这样工作:

def modmuladdct(ls, x, y, k):
    result = 0

    # split up into congruence classes
    congruence_class = {}
    for v in ls:
        if v % k not in congruence_class:
            congruence_class[(v % k)] = [v]
        else:
            congruence_class[v % k].append(v)

    for n in congruence_class.keys():
        # congruence class to match addition
        m = (x - n + k) % k

        # check if congruence class matches for multiplication
        if (n * m % k != y) or len(congruence_class[m]) == 0:
            continue    # no matching congruence class

        # total number of pairs that will be built
        result += len(congruence_class[n]) * len(congruence_class[m])

    # divide by two since each pair would otherwise be counted twice
    return result // 2

每一对在结果中恰好出现两次:一次按顺序出现，一次按相反顺序出现。通过将结果除以二，这得到了纠正。运行时间是 O(n + k) (假设字典操作是 O(1) )。