理解数组中可被K整除的数对数量

Question

我正在阅读这个链接，并看到了计算可被k整除的一对数的代码。

使用了以下方法：

一种高效的方法是使用哈希技术。我们将元素分成不同的桶，具体取决于它们的（值 mod K）。当一个数被K整除时，余数可能为0、1、2、直到（k-1）。因此，我们可以采用大小为K的数组freq[]（初始化为0），并增加freq[A[i]%K]的值，以便我们可以计算出在与K相除时给出余数j的值的数量。

以下是代码：

public static int countKdivPairs(int A[], int n, int K) 
    { 
        // Create a frequency array to count 
        // occurrences of all remainders when 
        // divided by K 
        int freq[] = new int[K]; 
  
        // Count occurrences of all remainders 
        for (int i = 0; i < n; i++) 
            ++freq[A[i] % K]; 
  
        // If both pairs are divisible by 'K' 
        int sum = freq[0] * (freq[0] - 1) / 2; 
  
        // count for all i and (k-i) 
        // freq pairs 
        for (int i = 1; i <= K / 2 && i != (K - i); i++) 
            sum += freq[i] * freq[K - i]; 
        // If K is even 
        if (K % 2 == 0) 
            sum += (freq[K / 2] * (freq[K / 2] - 1) / 2); 
        return sum; 
    } 

我能理解代码的逐行执行过程，但我不明白代码中的逻辑是如何解决问题陈述的。

为什么我们要执行这些步骤：

1) int sum = freq[0] * (freq[0] - 1) / 2; 
2) sum += freq[i] * freq[K - i]; 
3)             if (K % 2 == 0) 
                sum += (freq[K / 2] * (freq[K / 2] - 1) / 2); 

请您提供一份解释吗？

- learner

Answer 1

这个问题是要找出所有满足和能被K整除的数对。

背景：

假设数对(a, b)是其中之一。那么我们有

(a + b) % K == 0

假设：

a % K = p
b % K = q

p和q可以是任何在[0, K-1]之间的正整数。

但重要的是，你认为p和q之间有关系吗？

有，因为a+b % K == 0。

a = xK + p
b = yK + q

**a + b = (x+y)K + (p+q)**

But we already know that a+b is divisible by K.
That clearly means:

p + q = K or p + q = 0 (remember that both p, q is within [0, K-1])

回到你的问题：

1) int sum = freq[0] * (freq[0] - 1) / 2; 
2) sum += freq[i] * freq[K - i]; 
3)             if (K % 2 == 0) 
                sum += (freq[K / 2] * (freq[K / 2] - 1) / 2); 

所以上述循环的目的是寻找所有可能的配对，使得余数为p和K-p，其中p的值在[0, K-1]之间。

- Serial Lazer

---

我清楚地理解了背景。感谢您的解释。但是“回到你的问题”，您能否进一步解释一下，为什么我们必须在第2步中进行乘法运算？为什么第1步和第3步是这样的，以及为什么我们在第3步中有一个if条件语句？ - learner

桶：freq[i]（记为B1）是具有余数i的项目数量。同样，freq[K-i]（记为B2）。现在，来自B1的每个项目都可以与来自B2的每个项目形成一对。因此，所有可能的有效配对将是|B1| x |B2|。 - Serial Lazer

第三步只是为了确保您不会重复计算。 - Serial Lazer

完美。现在为什么在步骤1和步骤3中要使用“/2”？ - learner

那就是 nc2.. 从 N 个物品中选择 2 个物品的方式数量。nc2 = n*(n-1)/2 - Serial Lazer