-1

n给你一个整数数组a0, a1, .. an和一个正整数k。找出并打印出(i,j)和可被(Whis )i+j整除的对数。这个问题是从这里开始的。ki+j % k == 0

我们需要O(n)及时解决。

一种解释是，我们可以通过根据它们的 mod 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

然后，据说：

现在，您可以像这样进行配对：具有 mod 3 == 0 的元素将与具有 (3 - 0) mod 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，在发布问题之前我不知道它的存在。

4

3 回答 3

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

于 2016-07-15T13:48:41.137 回答
1

您有n * (n - 1) / 2配对是因为每个人 ( n) 都可以与其他所有人 ( ) 配对n-1；但由于顺序无关紧要，我们避免通过除以二来计算镜像对。

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

答案很聪明，你可以通过低级优化让它快几个百分点；例如通过 3 实现一个专用模块，而不是依赖于 的通用算法%；但是您无法真正击败O(n)，因为您需要至少扫描每个元素一次，并且该解决方案已经做得不多了。（事实上​​，当你被要求写出结果时，在我看来你不能O(n^2)仅仅因为这个而做不到......）

这些问题都与python无关。你知道有一个math.stackexchange.com吗？

于 2016-07-15T13:36:46.543 回答
0

该解决方案适用于较大的 K 值。对于较小的值，Laurent 的解决方案更好。

def numPairsDivisibleByK(arr, k): freq = [0 for i in range(k)] for i in arr: freq[i % k] += 1

count = int(freq[0] * (freq[0] - 1) / 2)
for i in range(1, int(k / 2) + 1):
    if i == 0:
        count += int(freq[0] * (freq[0] - 1) / 2)
    elif float(i) == (k/2):
        count += int(freq[int(k/2)] * (freq[int(k/2)] - 1) / 2)
    else:
        count += int(freq[i] * freq[k-i])   

return count

打印 numPairsDivisibleByK([30,20,150,100,40], 60)

于 2019-03-17T04:00:58.233 回答