寻找可被整数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非常大,那么天真的算法会更好.