PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: raysh07
Tester: airths
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
None
PROBLEM:
You have N boxes each of chocolates and candies. The counts of candies in each of these boxes are represented by arrays A and B.
Count the number of ways to choose exactly one box of candies and one box of chocolates so that the total number of treats can be distributed equally among M children.
EXPLANATION:
If candy box i and chocolate box j are chosen, Chef will have a total of (A_i + B_j) chocolates.
This can be distributed equally to M children if and only if it’s a multiple of M.
Let’s fix i, the candy box that’s chosen.
Now, we’d like to count the number of j such that (A_i + B_j) is a multiple of M.
In other words, (A_i + B_j) should have a remainder of 0 when divided by M.
Observe that for this to be the case, B_j should have a remainder that’s “opposite” to that of A_i.
That is, the remainder when B_j is divided by M should be (M - A_i)\pmod M.
It’s not hard to see that we can choose any B_j that satisfies this property.
Let C be a 0-indexed array of length M, where C_x counts the number of indices j such that
B_j\pmod M = x
Then, following from our initial observations, for each i from 1 to N the number of valid indices j is exactly C_{(M - A_i)\pmod M}.
Computing the array C can be done in linear time, and finding the answer after that also takes linear time since we use a single lookup to array C for each i.
TIME COMPLEXITY:
\mathcal{O}(N + M) per testcase.
CODE:
Editorialist's code (Python)
for _ in range(int(input())):
n, m = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))
ct = [0]*m
for i in range(n):
a[i] %= m
b[i] %= m
ct[a[i]] += 1
ans = 0
for i in range(n):
ans += ct[(m - b[i])%m]
print(ans)