Codeforces Round 930 (Div. 2) |
---|
Закончено |
Задан массив $$$a_1, a_2, \ldots, a_n$$$. Изначально $$$a_i=i$$$ для всех $$$1 \le i \le n$$$.
Для произвольного целого $$$k \ge 2$$$ операция $$$\texttt{swap}(k)$$$ устроена следующим образом:
Выполним операции $$$\texttt{swap}(i)$$$ для каждого $$$i=2,3,\ldots, n$$$ именно в таком порядке. Найдите позицию, на которой в результате окажется число $$$1$$$. Иными словами, найдите такое $$$j$$$, что $$$a_j = 1$$$ после всех операций.
$$$^\dagger$$$ Целое число $$$x$$$ называется делителем числа $$$y$$$, если существует целое $$$z$$$, для которого $$$y = x \cdot z$$$.
Каждый тест состоит из нескольких наборов входных данных. В первой строке находится одно целое число $$$t$$$ ($$$1 \le t \le 10^4$$$) — количество наборов входных данных. Далее следует описание наборов входных данных.
Единственная строка каждого набора входных данных содержит одно целое число $$$n$$$ ($$$1 \le n \le 10^9$$$) — длину массива $$$a$$$.
Для каждого набора входных данных выведите позицию, на которой окажется число $$$1$$$.
4145120240229
1 4 4 67108864
В первом наборе входных данных массив равен $$$[1]$$$, и никакие операции не выполняются.
Во втором наборе входных данных $$$a$$$ изменяется следующим образом:
Итак, число $$$1$$$ находится на позиции $$$4$$$ (то есть $$$a_4 = 1$$$). Значит, ответ равен $$$4$$$.
Название |
---|