Trò Chơi Số (Number Game)

Hướng tiếp cận

Đây là bài toán lý thuyết trò chơi đơn giản. Phân tích từng trường hợp của $n$ để tìm thuật chiến thắng.

Nhận xét quan trọng

1. $n=1$: $A$ không thể đi → $A$ thua.
2. $n=2$: $A$ trừ $1$ → $B$ chỉ còn $n=1$, thua.
3. $n$ lẻ và $n>1$: $A$ chia cho chính $n$ → $n=1$, $B$ thua.
4. $n$ là luỹ thừa của $2$ ($n=2^k$, $k\ge 2$): $n$ không có ước lẻ lớn hơn $1$, $A$ chỉ trừ được $1$ → $n$ lẻ. $B$ chia thắng → $A$ thua.
5. $n=2·p$ với $p$ là số nguyên tố lẻ: nếu $A$ chia cho $p$ → $n=2$ → $B$ trừ $1$ thắng. Nếu $A$ trừ $1$ → $n$ lẻ, $B$ chia thắng. Mọi nước đi đều thua → $A$ thua.
6. Các trường hợp còn lại: $n$ chẵn, không là luỹ thừa của $2$, và không có dạng $2·p$. Khi đó $A$ luôn có thể chia $n$ cho một ước lẻ $d>1$ sao cho $n/d$ là luỹ thừa của $2$ lớn hơn $2$ — đẩy $B$ vào trạng thái thua (luỹ thừa của $2$, $\ge 4$). Vậy $A$ thắng.

Thuật toán

Với mỗi $n$, kiểm tra theo thứ tự các trường hợp trên. Việc kiểm tra số nguyên tố thực hiện bằng thử chia tới $\sqrt{n}$.

Độ phức tạp

• Thời gian: $O(t·\sqrt{n})$ ở trường hợp xấu nhất.
• Bộ nhớ: $O(1)$.