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

Question

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

我不知道 n 和 k 的界限。因此，为简单起见，假设 n 和 k 不是很大。

不用说，尽可能给出最优的解决方案。（我知道天真的方法:-)！)

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很大，则朴素算法更好。

Answer 2

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