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 | 無額外限制。 |