Tóm tắt đề bài

Cho \(3\) số nguyên dương \(a, b, n\). Tìm số nguyên dương nhỏ nhất \(k \ge n\) sao cho:

• \(k\) chia hết cho \(a\)
• \(k\) không chia hết cho \(b\)

Nếu không tồn tại, in \(-1\).

Phân tích

• Ràng buộc lớn: \(a, b \le 10^9\), \(n \le 10^{16}\) nên không thể duyệt từng số từ \(n\) trở đi.
• Các số chia hết cho \(a\) có dạng \(k = a \cdot t\).
• Ta cần tìm bội nhỏ nhất của \(a\) không nhỏ hơn \(n\), sau đó (nếu bội đó lại chia hết cho \(b\)) thì tăng thêm \(a\) cho đến khi không còn chia hết cho \(b\).

Nhận xét quan trọng (trường hợp vô nghiệm)

Nếu \(a\) chia hết cho \(b\) (tức \(a \bmod b = 0\)) thì mọi bội của \(a\) đều chia hết cho \(b\):

• Vì \(a = b \cdot x\) \(\Rightarrow\) \(k = a \cdot t = b \cdot (x t)\).

Do đó không thể có \(k\) thỏa mãn “chia hết cho \(a\) nhưng không chia hết cho \(b\)”, kết quả là \(-1\).

Hướng giải quyết

Ý tưởng

1. Nếu \(a \bmod b = 0\) thì in \(-1\) ngay.
2. Ngược lại:

3. Tìm bội nhỏ nhất của \(a\) không nhỏ hơn \(n\): \(k = \left\lceil \frac{n}{a} \right\rceil \cdot a\)

   Trong code AC, việc này được tính bằng:

   • Lấy \(k = \left\lfloor \frac{n}{a} \right\rfloor \cdot a\)
   • Nếu \(k < n\) thì \(k += a\)
   • Nếu \(k \bmod b = 0\) thì cộng thêm \(a\) cho đến khi \(k \bmod b \ne 0\).

Tại sao vòng while sẽ nhanh?

Xét các giá trị thử: \(k, k+a, k+2a, \dots\). Xét theo modulo \(b\):

• Vì \(a \bmod b \ne 0\), dãy \(k + t a \pmod b\) sẽ không thể luôn luôn bằng \(0\).
• Thực tế, số bước tối đa trước khi gặp một số không chia hết cho \(b\) là không quá \(b\) (vì có tối đa \(b\) giá trị modulo), và thường rất nhỏ.

Thuật toán (đúng theo code AC)

1. Đọc \(a, b, n\).
2. Nếu \(a \bmod b = 0\):
   • In -1.
3. Ngược lại:
   • \(k = (n // a) * a\)
   • Nếu \(k < n\) thì \(k = k + a\)
   • Trong khi \(k \bmod b = 0\):
     • \(k = k + a\)
   • In \(k\).

Lưu ý/Pitfall

• Dùng kiểu số nguyên đủ lớn: Python an toàn; nếu C++ cần long long (vì \(n\) tới \(10^{16}\)).
• Không được duyệt từ \(n\) từng bước \(1\).

Độ phức tạp

• Thời gian: trung bình rất nhanh; về lý thuyết vòng lặp tăng theo bước \(a\) và số lần lặp bị chặn bởi \(O(b)\) trong trường hợp xấu.
• Bộ nhớ: \(O(1)\).