Codeforces Round #697 (Div. 3) - A & B

 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).

Code mẫu (C++).

---

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.

Code mẫu (C++).

---

Happy coding!