Странная последовательность

Заметим, что если $$$n \equiv 2$$$ $$$(mod$$$ $$$3)$$$, то мы можем узнать $$$(n - 1)$$$-е число последовательности и умножить его на $$$2$$$. Аналогично, если $$$n \equiv 0$$$ $$$(mod$$$ $$$3)$$$, то мы можем узнать $$$(n - 2)$$$-е число последовательности и умножить его на $$$3$$$. Поэтому, давайте сделаем $$$n = \lceil \frac{n}{3} \rceil$$$ и будем далее рассматривать последовательность $$$1, 4, 5, 6, 7, 9, ..$$$.

Утверждается, что все числа в последовательности имеют вид $$$2^x \cdot 3^y \cdot p$$$, где $$$p$$$ — натуральное число, не делящееся на $$$2$$$ и на $$$3$$$, а $$$(x + y)$$$ — чётно. Это легко доказать по индукции. Теперь заметим, что наша последовательность монотонна (в нашем случае строго возрастает), поэтому мы можем применить бинарный поиск. Для числа $$$mid$$$ мы должны узнать, сколько чисел в последовательности стоят до него. Переберём значения $$$x$$$ и $$$y$$$ и убедимся в том, что $$$(x + y)$$$ чётно. Теперь ответим на вопрос — сколько чисел вида $$$2^x \cdot 3^y \cdot a$$$ ($$$a$$$ – это любое натуральное число) меньше или равны $$$x$$$? Оказывается, их $$$al_{xy} = \lfloor \frac{mid}{2^x \cdot 3^y} \rfloor$$$. Теперь нам нужно из этого количества вычесть все числа, у которых $$$a$$$ делится на $$$2$$$ или на $$$3$$$. Делается это так: $$$al_{xy} = al_{xy} - (\lfloor \frac{al_{xy}}{2} \rfloor + \lfloor \frac{al_{xy}}{3} \rfloor - \lfloor \frac{al_{xy}}{6} \rfloor$$$). Просуммировав значения $$$al_{xy}$$$ для всех чисел $$$(x, y)$$$, мы получим искомую величину $$$vid$$$ (сколько чисел в последовательности стоят до числа $$$mid$$$). Если $$$vid < n$$$, то сдвинем левую границу бинпоиска, иначе правую.

Когда бинпоиск отработает, его правая граница и будет ответом на задачу. Не забываем, что иногда ответ надо будет домножить на $$$2$$$ или на $$$3$$$.