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