两个数的和是否可被除以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很大，那么朴素的算法会更好。