Hướng dẫn giải của [KHTN - TS10 - 2025] Bài 2: Số dư
Chỉ dùng lời giải này khi không có ý tưởng, và đừng copy-paste code từ lời giải này. Hãy tôn trọng người ra đề và người viết lời giải.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Nộp một lời giải chính thức trước khi tự giải là một hành động có thể bị ban.
Tóm tắt đề bài
Cho số nguyên dương ~n~. Hãy tính số dư của ~2^{3^n}~ khi chia cho ~5~.
Lời giải
Ta thấy:
- ~2^0~ chia ~5~ dư ~1~.
- ~2^1~ chia ~5~ dư ~2~.
- ~2^2~ chia ~5~ dư ~4~.
- ~2^3~ chia ~5~ dư ~3~.
- ~2^4~ chia ~5~ dư ~1~.
- ...
Vì vậy ta cần quan tâm tới số dư khi chia ~3^n~ cho ~4~.
- Với ~n~ chẵn, ~3^n~ sẽ là số chính phương, mà số chính phương lẻ chia ~4~ luôn dư ~1~. Vì vậy, ~2^{3^n}~ chia ~5~ dư ~2~.
- Ngược lại, với ~n~ lẻ, ~3^n~ chia ~4~ dư ~1 \times 3 = 3~. Vì vậy, ~2^{3^n}~ chia ~5~ dư ~3~.
Độ phức tạp: ~O~ (~1~).
Bình luận