Загадка Прайма

Автор задачи и разработчик: Герман Андосов

Заметим, что если $$$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, \ldots$$$.

Утверждается, что все числа в последовательности имеют вид $$$2^x \cdot 3^y \cdot p$$$, где $$$p$$$ — натуральное число, не делящееся на $$$2$$$ и на $$$3$$$, а $$$(x + y)$$$ — четно. Это легко доказать по индукции.

Теперь заметим, что наша последовательность монотонна (в нашем случае строго возрастает), поэтому мы можем применить бинарный поиск. Для числа $$$mid$$$ мы должны узнать, сколько чисел в последовательности стоят до него. Переберем значения $$$x$$$ и $$$y$$$, и убедимся в том, что $$$(x + y)$$$ четно. Теперь ответим на вопрос — сколько чисел вида $$$2^x \cdot 3^y \cdot a$$$ меньше или равны $$$x$$$? Оказывается, их $$$$$$T(x, y) = \left\lfloor \frac{mid}{2^x \cdot 3^y} \right\rfloor \text{.}$$$$$$

Теперь нам нужно из этого количества вычесть все числа, у которых $$$a$$$ делится на $$$2$$$ или на $$$3$$$. Делается это по формуле включений-исключений: $$$$$$T(x, y) \gets T(x, y) - \left(\left\lfloor \frac{T(x, y)}{2} \right\rfloor + \left\lfloor \frac{T(x, y)}{3} \right\rfloor - \left\lfloor \frac{T(x, y)}{6} \right\rfloor \right) \text{.}$$$$$$.

Просуммировав значения $$$T(x, y)$$$ для всех чисел $$$(x, y)$$$, мы получим искомую величину $$$cnt$$$ (сколько чисел в последовательности стоят до числа $$$mid$$$). Если $$$cnt < n$$$, то сдвинем левую границу бинпоиска, иначе правую. Когда бинпоиск отработает, его правая граница и будет ответом на задачу. Не забываем, что иногда ответ надо будет домножить на $$$2$$$ или на $$$3$$$.