Pairs with Divisible Sum
National Olympiad — National round (2020 season)
Submission name: pairs.cpp
Problem summary
Count pairs formed by choosing one element from each of two sequences such that their sum is divisible by d. Equal values at different positions count separately.
Input
d; N and the first N values; M and the second M values.
Output
The number of qualifying pairs.
Constraints
1 < d < 50,000; 1 < N,M < 100,000; 0 ≤ values < 50,000.
Worked example
An independently prepared example for this explanation.
Input
3 2 5 3 3 3 4 3
Output
3
Solution analysis
- Only remainders modulo d matter. Store how many values of the first sequence have each remainder r.
- For a second-sequence value with remainder s, its partner must have remainder (d−s) mod d. Add that frequency to a 64-bit answer; no actual pairs need to be stored.
- In the sample, first-sequence remainders are 2 and 0. Each of the two 3 values matches the first-sequence 3, and 4 matches 5. This gives 1 + 1 + 1 = 3 pairs.
Why it works
A sum is divisible by d exactly when its two remainders add to 0 modulo d. The frequency lookup counts every eligible first position for each second position, so each valid pair is counted exactly once.
Watch out. The complement of remainder 0 is 0, not d. The answer may exceed a signed 32-bit integer.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int d, n;
cin >> d >> n;
vector<long long> count(d, 0);
for (int i = 0; i < n; i++) {
int value;
cin >> value;
count[value % d]++;
}
int m;
cin >> m;
long long answer = 0;
for (int i = 0; i < m; i++) {
int value;
cin >> value;
// Remainder zero also needs complement zero.
answer += count[(d - value % d) % d];
}
cout << answer << '\n';
}