Editorial for Bedao Regular Contest 02 - SISTER


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

Để tránh TLE đầu tiên ta sẽ dùng sàng nguyên tố để tìm tất cả các số nguyên tố từ thuộc khoảng ~[1, 10^6]~

Vì ~ 1 \leq n \leq 20~ nên ta có thể nghĩ đến thuật toán quay lui - nhánh cận hoặc duyệt nhị phân bằng bitmask, do duyệt bitmask có phần tiện hơn nên solution sẽ hướng dẫn theo hướng này

Mỗi lần duyệt, ta sẽ có ~2~ biến là ~S_1~ và ~S_2~, Nếu như bit thứ ~i~ là ~1~ thì ta cộng vào ~S_1~, ngược lại thì cộng vào ~S_2~ và sau mỗi lần duyệt ta sẽ tính chênh lệch của ~S_1~ và ~S_2~ là ~T = |S_1-S_2|~ và nếu ~T~ là nguyên tố thì thỏa mãn và ta sẽ lấy đáp án tốt nhất sau ~2^n~ lần duyệt.

Độ phức tạp: ~O(2^n)~


Comments

Please read the guidelines before commenting.


There are no comments at the moment.