Nhận xét

• Số lần lật quả trứng thứ ~n~ sẽ bằng số ước của ~n~
• Vì trạng thái ban đầu của quả trứng là ngửa, nên nếu số lần lật là lẻ, quả trứng sẽ ở trạng thái úp xuống. Ngược lại, quả trứng sẽ ở trạng thái ngửa.
• Chỉ các số chính phương mới có số ước là số lẻ. Các số không phải số chính phương có số ước là số chẵn.

Cách làm

• Subtask 1: Vì ~n~ khá nhỏ nên ta sinh một mảng ~a[n]~ có các giá trị ban đầu bằng 0. Với các giá trị từ ~1~ đến ~n~, phần tử nào trong mảng chia hết cho ~n~ thì biến đổi phần tử đó. Độ phức tạp ~\mathcal{O}(n^2)~
• Subtask 2: Dùng 1 vòng for để đếm số ước của ~n~. Nếu số ước là số chẵn thì quả trứng thứ ~n~ sẽ ở trạng thái ngửa và ngược lại. Độ phức tạp: ~\mathcal{O}(\sqrt{n})~
• Subtask 3: Chúng ta sẽ cải tiến subtask 2. Xét ~n~ có phải số chính phương hay không. Nếu ~n~ là số chính phương thì quả trứng thứ ~n~ sẽ ở trạng thái ngửa và ngược lại. Độ phức tạp: ~\mathcal{O}(1)~