Bài 2: Đếm ngày chia hết cho K (THT A Thừa Thiên Huế 2026)
Xem PDFAn hiện đang có \(N\) viên bi. Mỗi ngày, bố của An cho An thêm \(3\) viên bi. An muốn biết cần chờ ít nhất bao nhiêu ngày nữa để tổng số bi của mình là một số chia hết cho \(K\).
Yêu cầu
Hãy tính số ngày ít nhất để tổng số bi của An chia hết cho \(K\). Trong trường hợp không bao giờ số bi của An có thể chia hết cho \(K\), hãy in ra X.
Input
- Gồm hai số tự nhiên \(N\) và \(K\) (\(1 \le N, K \le 10^{15}\)). Mỗi số trên một dòng.
Output
- In ra một số là số ngày ít nhất tìm được. Nếu không tồn tại số ngày thỏa mãn, in ra
X.
Example
Test 1
Input
5
4Output
1Note
Ban đầu An có \(5\) viên bi. Sau \(1\) ngày, bố cho thêm \(3\) viên bi, An có \(5 + 3 = 8\) viên bi. Vì \(8\) chia hết cho \(4\) nên số ngày ít nhất cần chờ là \(1\) ngày.
Test 2
Input
4
6Output
XNote
Số bi của An qua các ngày lần lượt là: \(4, 7, 10, 13, 16, 19, \dots\) Ta thấy số bi của An sẽ không bao giờ chia hết cho \(6\). Cần in ra X.
Test 3
Input
18
9Output
0Note
Ban đầu An có \(18\) viên bi. Vì \(18\) đã chia hết cho \(9\), nên An không cần chờ thêm ngày nào. Số ngày ít nhất là \(0\).
Scoring
- Subtask \(1\) (\(40\%\) số điểm): \(1 \le N, K \le 10^4\).
- Subtask \(2\) (\(30\%\) số điểm): \(1 \le N, K \le 10^7\).
- Subtask \(3\) (\(30\%\) số điểm): Không có ràng buộc gì thêm.
Bình luận