在O（n）时间的数组中找到可分式总和对

Question

给出一个n整数a0, a1, .. an和一个正整数k的数组。查找和打印(i,j)对的数量，其中i+j可被k（即i+j % k == 0）均分。此问题已从here中取得。

我们需要O(n)时间的解决方案。

一个解释是，我们可以通过将元素分成桶来根据他们的模块k来做到这一点。例如，你具备的要素：1 3 2 6 4 5 9 and k = 3

mod 3 == 0 : 3 6 9 
mod 3 == 1 : 1 4 
mod 3 == 2 : 2 5 

然后，说：

现在，你可以对像这样：与国防部3 == 0元素将匹配 与元素（3 - 0）模K = 0，在MOD 3 == 0列表，以便其他元件，像这样： （3,6）（3,9）（6,9）

此外：

将会有n *（n-1）/ 2个这样的对，其中n是 列表的长度，因为列表是相同的并且i！= j。 mod 3 == 1的元素将与（3-1）mod k = 2的元素匹配，因此 mod 3 == 2列表中的元素如下所示：（1,2）（1,5）（4 ，2）（4，5）

它是有道理的(3, 6) (3, 9) (6, 9) (all items in the 0th bucket be paired)自(a + b)% k = 0 = a % k + b % k。

什么是不明确的是，其他对是如何通过组合第一（mod 3 == 1）和第二（mod 3 == 2）桶中的元素生成的，为什么会有n *（n - 1）/ 2对。 是否有另一种（更好）的方法？

这个问题适用于Math Stackexchange，这个问题在发布问题之前并不知晓。

Answer 1

您有n * (n - 1)/2双，因为每个人（n）都可以与其他人配对（n-1）;但由于顺序无关紧要，所以我们避免将镜像对除以二。

当分子相加时，同一商的余数相加，但提示不能超过商。在3的划分中提醒3实际上是0的提醒。

答案是非常聪明的，你可以使它在低级别优化中快几个百分点;例如实现专用的模块3而不是依靠%的通用算法;但是你不可能击败O(n)，因为你需要扫描每个元素至少一次，并且解决方案已经不再做太多了。 （实际上，因为你被要求写的结果，在我看来，你不能在低于O(n^2)，正因为如此... ...）

这些问题都与python没有任何关系。你知道吗有math.stackexchange.com？

Answer 2

我翻译的C代码...

using namespace std; 
int main(){ 

    int n; 
    int k; 
    cin >> n >> k; 
    int a[n]; 
    int m[k]; 
    for(int i=0; i<k; i++) 
     m[i]=0; 
    for(int i = 0; i < n; i++){ 
     cin >> a[i]; 
     m[a[i]%k]++; 
    } 
    int sum=0; 
    sum+=(m[0]*(m[0]-1))/2; 
    for(int i=1; i<=k/2 && i!=k-i; i++){ 
     sum+=m[i]*m[k-i]; 
    } 
    if(k%2==0) 
     sum+=(m[k/2]*(m[k/2]-1))/2; 
    cout<<sum; 
    return 0; 
} 

成Python：

def divisible_sum_pairs(n, k, a_list): 
    m = [0] * len(a_list) 
    for a in a_list: 
     m[a % k] += 1 

    sum = int(m[0] * (m[0] - 1)/2) 
    for i in range(1, int(k/2) + 1): 
     if i != k - 1: 
      sum += m[i] * m[k - i] 
    if k % 2 == 0: 
     sum += m[int(k/2)] * (m[int(k/2)] - 1)/2 

    return sum 

有了：

print(divisible_sum_pairs(6, 3, [1, 3, 2, 6, 1, 2])) 

你得到5