# 算法题：对数组中的对进行计数，其和可被K整除

2021年4月21日15:46:08 发表评论 981 次浏览

## 本文概述

``````Input : A[] = {2, 2, 1, 7, 5, 3}, K = 4
Output : 5
Explanation :
There are five pairs possible whose sum
is divisible by '4' i.e., (2, 2), (1, 7), (7, 5), (1, 3) and (5, 3)

Input : A[] = {5, 9, 36, 74, 52, 31, 42}, K = 3
Output : 7``````

## C++

``````//C++ Program to count pairs
//whose sum divisible by 'K'
#include <bits/stdc++.h>
using namespace std;

//Program to count pairs whose sum divisible
//by 'K'
int countKdivPairs( int A[], int n, int K)
{
//Create a frequency array to count
//occurrences of all remainders when
//divided by K
int freq[K] = { 0 };

//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 * (freq - 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;
}

//Driver code
int main()
{

int A[] = { 2, 2, 1, 7, 5, 3 };
int n = sizeof (A) /sizeof (A);
int K = 4;
cout <<countKdivPairs(A, n, K);

return 0;
}``````

## Java

``````//Java program to count pairs
//whose sum divisible by 'K'
import java.util.*;

class Count {
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;
}
public static void main(String[] args)
{
int A[] = { 2 , 2 , 1 , 7 , 5 , 3 };
int n = 6 ;
int K = 4 ;
System.out.print(countKdivPairs(A, n, K));
}
}``````

## Python3

``````# Python3 code to count pairs whose
# sum is divisible by 'K'

# Function to count pairs whose
# sum is divisible by 'K'
def countKdivPairs(A, n, K):

# Create a frequency array to count
# occurrences of all remainders when
# divided by K
freq = [ 0 ] * K

# Count occurrences of all remainders
for i in range (n):
freq[A[i] % K] + = 1

# If both pairs are divisible by 'K'
sum = freq[ 0 ] * (freq[ 0 ] - 1 ) /2 ;

# count for all i and (k-i)
# freq pairs
i = 1
while (i <= K //2 and i ! = (K - i) ):
sum + = freq[i] * freq[K - i]
i + = 1

# If K is even
if ( K % 2 = = 0 ):
sum + = (freq[K //2 ] * (freq[K //2 ] - 1 ) /2 );

return int ( sum )

# Driver code
A = [ 2 , 2 , 1 , 7 , 5 , 3 ]
n = len (A)
K = 4
print (countKdivPairs(A, n, K))``````

## C#

``````//C# program to count pairs
//whose sum divisible by 'K'
using System;

class Count
{
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 * (freq - 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;
}

//Driver code
static public void Main ()
{
int []A = { 2, 2, 1, 7, 5, 3 };
int n = 6;
int K = 4;
Console.WriteLine(countKdivPairs(A, n, K));
}
}

//This code is contributed by akt_mit.``````

## PHP

``````<?php
//PHP Program to count pairs
//whose sum divisible by 'K'

//Program to count pairs whose sum
//divisible by 'K'
function countKdivPairs( \$A , \$n , \$K )
{

//Create a frequency array to count
//occurrences of all remainders when
//divided by K
\$freq = array_fill (0, \$K , 0);

//Count occurrences of all remainders
for ( \$i = 0; \$i <\$n ; \$i ++)
++ \$freq [ \$A [ \$i ] % \$K ];

//If both pairs are divisible by 'K'
\$sum = (int)( \$freq  * ( \$freq  - 1) /2);

//count for all i and (k-i)
//freq pairs
for ( \$i = 1; \$i <= \$K /2 &&
\$i != ( \$K - \$i ); \$i ++)
\$sum += \$freq [ \$i ] * \$freq [ \$K - \$i ];

//If K is even
if ( \$K % 2 == 0)
\$sum += (int)( \$freq [(int)( \$K /2)] *
( \$freq [(int)( \$K /2)] - 1) /2);
return \$sum ;
}

//Driver code
\$A = array ( 2, 2, 1, 7, 5, 3 );
\$n = count ( \$A );
\$K = 4;
echo countKdivPairs( \$A , \$n , \$K );

//This code is contributed by mits
?>``````

``5`` 