Editorial for Bedao Mini Contest 12 - BINARY


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

Để thoả mãn cả ~3~ điều kiện thì ta có một cách dựng ~2~ số ~a~, ~b~ đơn giản như sau:

Xét một đoạn các bit ~1~ liên tiếp trong ~c~, gọi đoạn đó là đoạn ~[l, r]~. Vì ~2^{r+1} - 2^l = 2^l + 2^{l+1} + ... + 2^r~, nên ta chỉ cần thay đổi bit ~r + 1~ của ~a~ và bit ~l~ của ~b~ thành ~1~ ta sẽ thoả mãn điều kiện của đề bài.

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


Comments

Please read the guidelines before commenting.


There are no comments at the moment.