P15240 [NHSPC 2025] 解码密钥

在一电玩游戏里，有一个被称为「中央核心」的超级电脑控制着整个城市的运作。然而，最近中央核心被一道由恶意代码组成的防火墙锁住，城市陷入了瘫痪。 要解开这道防火墙，必须输入一个特定的「解锁码」。这个解锁码不是一个简单的数字，而是第 $n$ 个「有效数字」。这座城市共有 $k$ 台特殊的服务器，其中第 $i$ 台服务器带有一个独特的密钥 $p_i$。任何一个**正整数**，只要能被这 $k$ 个密钥中的至少一个整除，就可以被视为一个「有效数字」。 给定 $n$ 和 $p_1,p_2,\ldots ,p_k$，你的任务是找出第 $n$ 个「有效数字」，将其作为解锁码输入「中央核心」，以拯救这座城市。 举例来说，若 $n=10$、$k=3$ 且密钥为 $2, 3, 5$。则因为能被 $2, 3$ 或 $5$ 整除的数依次是 $2, 3, 4, 5, 6, 8, 9, 10, 12, 14\ldots$，而第 $10$ 个数是 $14$，因此所求为 $14$。

$$ \begin{aligned} &n \; k \\ &p_1 \; p_2 \; \dots \; p_k \end{aligned} $$ * $n$ 代表你要找出第 $n$ 个有效数字。 * $k$ 代表密钥的个数。 * $p_i$ 代表第 $i$ 把密钥的数值。

$$ans$$ * 输出一个正整数 $ans$，表示第 $n$ 个能被 $p_1,p_2,\ldots ,p_k$ 中至少一个数整除的数字。

### 数据限制 * $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}$。 * 保证所求答案 $\le 10^{18}$。 * 输入的数皆为整数。 ### 评分说明 本题共有四组子任务，条件限制如下所示。每一组可有一或多笔测试资料，该组所有测试资料皆需答对才会获得该组分数。 | 子任务 | 分数 | 额外输入限制 | | :------: | :----: | ------------ | | 1 | 2 | 保证所求答案 $\le 10^{6}$。 | | 2 | 27 | $n \le 10, k \le 2$。 | | 3 | 34 | $n \le 10^5$。 | | 4 | 37 | 无额外限制。 |