8548. Pair Sum Divisibility

You are given an array of integers A = (a₀, a₁, ..., a_n-1) and a positive integer k. Find the number of pairs (i, j) such that i < j and the sum a_i + a_j is divisible by k.

Input. The first line contains the integers n (2 ≤ n, k ≤ 100) and k. The second line contains n integers – the elements of the array A = (a₀, a₁, ..., a_n-1), where 1 ≤ a_i ≤ 100.

Output. Print the number of pairs (i, j) such that i < j and a_i + a_j is divisible by k.

Sample input	Sample output
6 3 1 3 2 6 1 2	5

SOLUTION

arrays

Algorithm analysis

Store the input sequence of numbers in an array.

Let res = 0. Then iterate over all pairs (i, j) with i < j. If a_i + a_j is divisible by k, increase res by 1.

Algorithm implementation

Declare an array m.

#define MAX 101

int m[MAX];

Read the input data.

scanf("%d %d", &n, &k);

for (i = 0; i < n; i++)

scanf("%d", &m[i]);

The variable res stores the number of required pairs.

res = 0;

Iterate over all pairs (i, j) with i < j. If a_i + a_j is divisible by k, increase res by 1.

for (i = 0; i < n; i++)

for (j = i + 1; j < n; j++)

if ((m[i] + m[j]) % k == 0) res++;

Print the answer.

printf("%d\n", res);