Reversed Divisible Pairs
National Olympiad — Regional round (2013 season)
Submission name: dcouples.cpp
Problem summary
Count unordered pairs of distinct n-digit positive numbers such that both are divisible by d and reversing one gives the other. Neither number may have a leading zero.
Input
Two integers n and d.
Output
The number of distinct valid unordered pairs.
Constraints
2 ≤ n ≤ 9; 2 ≤ d ≤ 1,000,000.
Worked example
An independently prepared example for this explanation.
Input
4 23
Output
4
Solution analysis
- Split a number into h=floor(n/2) outer digits on each side and an optional middle digit c. Write it as A*P+C+reverse(B), where A and B are h-digit numbers with nonzero first digits, P=10^(h+n%2), and C=c*10^h (or zero for even n). Its reverse is B*P+C+reverse(A).
- Count only A<B. This excludes palindromes and chooses exactly one orientation of every pair. Sweep B upward; before querying B, insert A=B−1 into a frequency map keyed by (A*P mod d, reverse(A) mod d). Thus the map contains exactly the permitted A values.
- For fixed B and c, divisibility requires the map key ((−reverse(B)−C) mod d,(−B*P−C) mod d). Add the frequency of this key. For n=4,d=23 the four pairs are (3358,8533),(4807,7084),(4968,8694),(7498,8947).
Why it works
Every nonpalindromic reversed pair has a unique orientation with A<B, since comparing the first h digits decides the order unless they agree, in which case the whole number is a palindrome. The map contains exactly all smaller valid h-digit A values. Its two residue equations are precisely divisibility of the number and its reverse, so each query counts all and only valid pairs once.
Watch out. Reversal of an h-digit block must conceptually keep h positions, even when its numeric reverse begins with zero. Both A and B must have h digits. Normalize negative remainders. Brute force over all 9-digit numbers is too slow.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <unordered_map>
using namespace std;
long long reverseDigits(long long value) {
long long result = 0;
while (value > 0) {
result = result * 10 + value % 10;
value /= 10;
}
return result;
}
int main() {
int n;
long long divisor;
cin >> n >> divisor;
int half = n / 2;
long long base = 1;
for (int i = 0; i < half; i++) {
base *= 10;
}
long long first = base / 10;
long long place = base * (n % 2 == 1 ? 10 : 1);
unordered_map<long long, long long> frequency;
long long answer = 0;
for (long long b = first; b < base; b++) {
// The map must contain exactly the outer blocks A < B.
if (b > first) {
long long a = b - 1;
long long key = (a * place % divisor) * divisor + reverseDigits(a) % divisor;
frequency[key]++;
}
int middleChoices = n % 2 == 1 ? 10 : 1;
for (int middle = 0; middle < middleChoices; middle++) {
long long center = middle * base;
// Match both divisibility residues simultaneously.
long long r1 = (divisor - (reverseDigits(b) + center) % divisor) % divisor;
long long r2 = (divisor - (b * place + center) % divisor) % divisor;
long long key = r1 * divisor + r2;
auto found = frequency.find(key);
if (found != frequency.end()) {
answer += found->second;
}
}
}
cout << answer << '\n';
}