Editorial for Bedao Mini Contest 08 - BOILEGG


Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.

Author: bedao

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

Comments

Please read the guidelines before commenting.


There are no comments at the moment.