Tutorial — Remainder Counting

Hãy chú ý đến điều kiện của phép chia lấy phần dư: số dư $b$ thu được khi chia $a$ cho $x$ luôn phải nhỏ hơn số chia $x$, tức là ta phải có $x > b$.

Đẳng thức $a \bmod x = b$ có nghĩa là $a - b$ phải chia hết cho $x$. Do đó, $x$ bắt buộc phải là một ước số nguyên dương của $a - b$ và thỏa mãn $x > b$.

Xử lý riêng các trường hợp $a = b$ (vô số nghiệm) và $a < b$ (không có nghiệm). Với $a > b$, ta có thể tìm tất cả các ước số của $a - b$ trong thời gian $O(\sqrt{a - b})$ và đếm xem có bao nhiêu ước lớn hơn $b$.