Останнє число#158

Останнє число (Розбір)

Простежимо за процесом. Спочатку викреслюються всі непарні числа, тобто залишаються — усі кратні двом. Далі викреслюються ті, що стоять на непарних місцях: із 2, 4, 6, 8, \ldots залишаються 4, 8, 12, \ldots — усі кратні чотирьом.

Закономірність зрозуміла: після кроків залишаються рівно ті числа з , які кратні 2^t. Процес зупиняється, коли залишиться одне число, — а це станеться на тому кроці, коли кратних 2^t буде рівно одне.

Останнє вціліле число — це найменше кратне свого степеня двійки, тобто сам степінь. Отже, відповідь — найбільший степінь двійки, що не перевищує :

2^{\lfloor \log_2 N \rfloor}.

Обчислити його найпростіше циклом: починаємо з k = 1 і подвоюємо, доки 2k \le N.

Оскільки сягає 10^{18}, обов'язково беріть 64-бітний тип; відповідь при цьому не перевищує 2^{59}.