P15240 [NHSPC 2025] Decode the Key.

In a video game, a supercomputer called the “Central Core” controls the operation of the entire city. However, recently the Central Core was locked by a firewall made of malicious code, and the city has fallen into paralysis. To break this firewall, you must enter a specific “unlock code”. This unlock code is not a simple number, but the $n$-th “valid number”. The city has $k$ special servers, and the $i$-th server comes with a unique key $p_i$. Any **positive integer** that is divisible by at least one of these $k$ keys can be considered a “valid number”. Given $n$ and $p_1,p_2,\ldots ,p_k$, your task is to find the $n$-th “valid number”, use it as the unlock code, and enter it into the “Central Core” to save the city. For example, if $n=10$, $k=3$, and the keys are $2, 3, 5$, then the numbers divisible by $2$, $3$, or $5$ are, in order, $2, 3, 4, 5, 6, 8, 9, 10, 12, 14\ldots$. The $10$-th number is $14$, so the answer is $14$.

$$ \begin{aligned} &n \; k \\ &p_1 \; p_2 \; \dots \; p_k \end{aligned} $$ * $n$ means you need to find the $n$-th valid number. * $k$ means the number of keys. * $p_i$ means the value of the $i$-th key.

$$ans$$ * Output a positive integer $ans$, representing the $n$-th number that is divisible by at least one number among $p_1,p_2,\ldots ,p_k$.

### Constraints * $1 \le n \le 10^9$. * $1 \le k \le 6$。 * $1 \le p_1\times p_2\times\cdots\times p_k \le 10^{18}$。 * It is guaranteed that the required answer is $\le 10^{18}$. * All input numbers are integers. ### Scoring This problem has four subtasks with the following constraints. Each subtask may contain one or more testdata files, and you will get the score for a subtask only if you answer all testdata in that subtask correctly. | Subtask | Score | Additional Input Constraints | | :-----: | :---: | ---------------------------- | | 1 | 2 | It is guaranteed that the required answer is $\le 10^{6}$。 | | 2 | 27 | $n \le 10, k \le 2$。 | | 3 | 34 | $n \le 10^5$。 | | 4 | 37 | No additional constraints. | Translated by ChatGPT 5