Round này bị lỗi server nên unrated. Nhưng bù lại, mình ngồi giải xong hôm sau tạch con mẹ nó xác suất.
---
A - Odd Divisor
Tóm tắt: Cho số nguyên n, xác định xem có tồn tại một ước số lẻ của n khác 1 hay không?
Hướng dẫn giải: Bài này đặt time limit là 2 second nên ta có thể giải bằng naive method hoặc observation.
- Naive method: Chừng nào n còn chia hết cho 2 thì n = n / 2. Cuối cùng nếu n = 1 thì không tồn tại ước số lẻ khác 1. Độ phức tạp cách này là O(logn), dư sức AC.
- Observation: Nếu n là một lũy thừa của 2 (2^x = n) thì không tồn tại ước số lẻ khác 1. Do đó, ta biến đổi bài toán về bài toán xác định xem n có phải là lũy thừa của 2 không. Với bài toán này, ta có thể dùng bitwise operation n & (n - 1). Độ phức tạp cho cách này là O(1).
---
B - New Year's Number
Tóm tắt: Cho số nguyên n, xác định xem có tồn tại cặp số nguyên (a, b) sao cho 2020a + 2021b = n hay không?
Hướng dẫn giải: 2020a + 2021b = n ⇔ 2020a = n - 2021b ⇔ a = (n - 2021b) / 2020 ∈ Z ≥ 0. Tức là, ta kiểm tra xem có tồn tại số nguyên a ≥ 0 sao cho a = (n - 2021b) / 2020.
---
Happy coding!
No comments:
Post a Comment