📜 WAYPOINT LESSON

Checkpoint — The Residue Ledger

⭐⭐⭐ advanced⏳ 20 min read📍 Lesson 258 of 281

Count pairs with sum divisible by d: the observation is that only residues matter — pair r with d−r, halve the self-paired residue, and the O(n²) scan disappears.

Điểm kiểm tra — Sổ cái phần dư. Count pairs (i < j) whose sum is divisible by d. The brute force checks all n·(n−1)/2 pairs; the observation is that two numbers are compatible exactly when their residues r and d−r pair up (r = 0 and r = d/2 pair with themselves). Count residues once, do combinatorics on d buckets. The wrong solution below counts every complementary residue pair TWICE (r vs d−r and d−r vs r) and forgets the self-pairing rule — find a sample where it disagrees.