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