List Removal
Xem PDF
Điểm:
1300
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
bàn phím
Output:
màn hình
Bạn được cho một dãy các số tự nhiên từ \(1\) đến \(n\) và một số nguyên \(k\). Bạn sẽ thực hiện một hoặc nhiều thao tác để xóa các số khỏi dãy này.
Trong mỗi thao tác, bạn xét các số hiện còn lại theo thứ tự tăng dần và xóa đi mỗi số thứ \(k\) (tức là số thứ \(k\), thứ \(2k\), thứ \(3k\),... trong danh sách hiện tại). Quá trình này kết thúc khi tổng số lượng số còn lại nhỏ hơn \(k\).
Nhiệm vụ của bạn là xác định thứ tự (chỉ số) của thao tác mà tại đó số \(n\) bị xóa. Nếu số \(n\) không bao giờ bị xóa cho đến khi quá trình kết thúc, in ra 0.
Input
- Dòng đầu tiên chứa số nguyên \(n\) (\(3 \le n \le 10^{18}\)).
- Dòng thứ hai chứa số nguyên \(k\) (\(2 \le k \le 100\)).
Output
- In ra một số nguyên duy nhất: chỉ số của thao tác mà \(n\) bị xóa, hoặc
0nếu \(n\) không bao giờ bị xóa.
Example
Test 1
Input
13
2Output
3Note
Giả sử \(n = 13\) và \(k = 2\):
- Thao tác 1: Xóa mỗi số thứ 2 từ dãy (1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13). Các số (2, 4, 6, 8, 10, 12) bị xóa. Còn lại: (1, 3, 5, 7, 9, 11, 13).
- Thao tác 2: Xóa mỗi số thứ 2 từ dãy (1, 3, 5, 7, 9, 11, 13). Các số (3, 7, 11) bị xóa. Còn lại: (1, 5, 9, 13).
- Thao tác 3: Xóa mỗi số thứ 2 từ dãy (1, 5, 9, 13). Các số (5, 13) bị xóa. Còn lại: (1, 9).
- Thao tác 4: Xóa mỗi số thứ 2 từ dãy (1, 9). Số (9) bị xóa. Còn lại: (1).
Vì chỉ còn lại 1 số và \(1 < k\), quá trình kết thúc. Trong ví dụ này, số 13 bị xóa ở thao tác thứ 3.
Bình luận