寻找可被给定整数k整除的数对所需的最佳算法

Question

给定n个整数和一个整数k，告诉有多少对给定的n个整数存在，使得这对中两个元素的和可被k整除？

我不知道n和k的范围。为了简单起见，假设n和k不是很大。

不用说，尽可能提供最优解（我知道朴素方法 :-)！）

- user1599964

Answer 1

两个数之和是否能被k整除，仅取决于它们对k取余的结果。

因此，如果k相对较小，您可以计算每个可能余数的数字数量，并从中计算出成对数量。假设k > 0且所有整数均为非负数。

unsigned long long combinations(unsigned k, unsigned long long *arr, unsigned n) {
    unsigned long long counts[k] = {0};
    unsigned i;
    for(i = 0; i < n; ++i) {
        ++counts[arr[i]%k];
    }
    // number of pairs where both are divisible by k
    unsigned long long combs = counts[0]*(counts[0]-1)/2;
    for(i = 1; i < (k+1)/2; ++i) {
        combs += counts[i]*counts[k-i];
    }
    if (k == 2*i) {
        combs += counts[i]*(counts[i] - 1)/2;
    }
    return combs;
}

该算法在O(n+k)步内完成。如果n较小而k很大，则朴素算法更好。

- Daniel Fischer

---

你比我快了 :) 不过，在做组合时，你需要使用counts[]而不是arr[]，并且需要考虑counts[0]。 - rici

太好了！线性时间...这正是我在寻找的...谢谢！ - user1599964

@rici 谢谢您的提醒。在combs的初始化中使用了counts[0]，我没有忘记（但是我还有一个错别字，“k-1”而不是“k-i”）。 - Daniel Fischer

Answer 2

除了Daniel Fischer所说的，如果k非常大，你可以对数字进行模k排序，然后从两端（在处理0 mod k值之后）向中间（k/2 mod k）遍历已排序的列表。这是O(n log n)，比O(n^2)好，假设你的朴素算法真的很朴素。

- rici

---

我的天真的二分搜索...所以这也是O(n log n)，但是是的，你的版本是一个改进...因为它只涉及到O(n log n)的排序...并且在线性O(n)时间内找到，而不是使用二分搜索的O(n log n)。谢谢！+1 :) - user1599964

你可以使用哈希表来代替排序/二分查找，以达到O(n)的时间复杂度。 - Keith Randall

@KeithRandall，是的，你可以尝试一下。我预计我的解决方案通常会更快，因为它的内部循环非常快，但我可能错了。如果你想尝试一下，我建议一个好的哈希函数是将整数模k模p，其中p是接近n的质数。这样可以将存储保持在O(n)的水平，与搜索和扫描相竞争。（当然，使用整数模k本身可以保证没有碰撞，但那么你就把问题简化成了Daniel的binsort，而在这种情况下我们已经放弃了它，因为bins占用太多内存。） - rici