Tóm tắt đề bài

Cho hai số nguyên dương \(N\) và \(K\). Hãy đếm số lượng số nguyên dương \(x \ge 1\) sao cho \(N \bmod x = K\). Nếu có vô hạn nghiệm thì in oo.

Phân tích

• Ta luôn có tính chất của phép chia dư:
  \(N \bmod x = K \Rightarrow 0 \le K < x\).
• Xét theo quan hệ giữa \(N\) và \(K\):
  1. Nếu \(N < K\): không thể có \(N \bmod x = K\) vì dư luôn \(\le N-1 < K\) với mọi \(x > N\) và nếu \(x \le N\) thì dư \(< x \le N < K\). Vậy đáp án \(=0\).
  2. Nếu \(N = K\): cần \(N \bmod x = N\). Điều này chỉ xảy ra khi \(x > N\) (khi đó \(N < x\) nên \(N \bmod x = N\)). Có vô hạn \(x\) như vậy, nên in oo.
  3. Nếu \(N > K\): đặt \(D = N - K > 0\) và khai thác dạng chia hết.

Hướng giải quyết

Nhận xét then chốt

Với \(N > K\), điều kiện

tương đương tồn tại thương \(q \ge 1\) sao cho

Suy ra

tức là \(x\) là ước của \(D = N-K\).

Ngoài ra từ điều kiện dư: \(K < x\).
Vậy trong trường hợp \(N > K\), bài toán trở thành:

• Đếm số ước dương \(x\) của \(D\) sao cho \(x > K\).

Thuật toán

1. Đọc \(N, K\).
2. Nếu \(N < K\): in 0.
3. Nếu \(N = K\): in oo.
4. Nếu \(N > K\):
   • Tính \(D = N - K\).
   • Duyệt \(i\) từ \(1\) đến \(\lfloor \sqrt{D} \rfloor\):
     • Nếu \(i\) không chia hết \(D\) thì bỏ qua.
     • Nếu \(i > K\) thì tăng đáp án.
     • Gọi \(j = D/i\) (ước đối của \(i\)).
       • Nếu \(j \ne i\) và \(j > K\) thì tăng đáp án.
5. In đáp án.

Vì sao phải kiểm tra \(x > K\)?

Nhiều bạn chỉ đếm ước của \(D\) mà quên điều kiện \(K < x\).
Ví dụ \(N=10, K=4\): \(D=6\) có các ước \(1,2,3,6\) nhưng chỉ \(6 > 4\) hợp lệ.

Độ phức tạp

• Thời gian: \(O(\sqrt{N-K})\) (tối đa khoảng \(10^6\) khi \(N,K \le 10^{12}\)).
• Bộ nhớ: \(O(1)\).