优化算法需要寻找对整除给定的整数k [英] Optimal Algorithm needed for finding pairs divisible by a given integer k

问题描述

给定n的整数和整数k，告诉多少这样对给定的n个整数的存在，使得在所述一对的两个要素的总和为整除用k？

Given n integers and an integer k, tell how many such pairs of the given n integers exist such that the sum of the two elements in the pair is divisible by k ?

我不知道对氮和钾的界限。所以，为简单起见，假设n和k不是非常大。

I don't know the bounds on n and k. So, for the sake of simplicity, assume n and k are not very large.

不用说，给作为最佳的解决方案成为可能。 （我知道这个天真的方法:-)！ ）

It goes without saying, give as optimal solution as possible. ( I know the naive method :-) ! )

推荐答案

无论是两个数的和是整除 K 只取决于他们的余数模<$ C $ ç> K 。

Whether the sum of two numbers is divisible by k only depends on their remainders modulo k.

因此​​，如果 K 是相当小的，你可以指望有多少数字有每一个可能的剩余部分，​​并计算出从对数。假设 K＆GT; 0 和所有非负整数

So if k is reasonably small, you can just count how many numbers have each possible remainder and compute the number of pairs from that. Assuming k > 0 and all integers nonnegative

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 非常大的，天真的算法比较好。

does the job in O(n+k) steps. If n is small and k very large, the naive algorithm is better.

这篇关于优化算法需要寻找对整除给定的整数k的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！