Count Pairs with Sum Divisible by K
Given an array A of N integers and an integer K, find the number of pairs (i, j) such that 0 <= i < j < N and (A[i] + A[j]) is divisible by K. You should count each such pair exactly once.
Input
The first line contains two integers N and K, separated by a space. The second line contains N integers representing the array A.
Output
Print a single integer, the count of pairs (i, j) such that 0 <= i < j < N and (A[i] + A[j]) % K == 0.
Constraints
1 <= N <= 200000 1 <= K <= 200000 0 <= A[i] <= 10^9
Example 1
6 3 1 2 3 4 5 6
5
Pairs are (1,2), (1,5), (2,4), (3,6), (4,5). Sums: 3, 6, 6, 9, 9. All divisible by 3. Count = 5.
Example 2
5 5 5 10 15 20 25
10
All elements are divisible by 5. Their remainders are 0. Any pair sums to a multiple of 5. Count = 5*(5-1)/2 = 10.
Hints
Similar problems
- Count Pairs with Equal Digit SumMedium
- Sum of Distinct ElementsMedium
- Count Pairs with Equal Digit GCDMedium
- Count Pairs with Equal Digit ProductMedium
- Two Sum Modulo KMedium
- Pairs with Sum Divisible by KMedium
More topics: Arrays problems, Hash Map and Hashing problems, Math and Number Theory problems
# Read the input from stdin and print the answer.
import sys
def main():
data = sys.stdin.read().split()
# your code here
main()
6 3 1 2 3 4 5 6
5 5 5 10 15 20 25