E. Prime Gift

Codeforces

IDCF912E

Time3000ms

Memory256MB

Difficulty—

binary searchdfs and similarmathmeet-in-the-middlenumber theorytwo pointers

English · Original

Chinese · Translation

Formal · Original

Opposite to Grisha's nice behavior, Oleg, though he has an entire year at his disposal, didn't manage to learn how to solve number theory problems in the past year. That's why instead of Ded Moroz he was visited by his teammate Andrew, who solemnly presented him with a set of _n_ **distinct prime** numbers alongside with a simple task: Oleg is to find the _k_\-th smallest integer, such that **all** its prime divisors are in this set. ## Input The first line contains a single integer _n_ (1 ≤ _n_ ≤ 16). The next line lists _n_ distinct prime numbers _p_1, _p_2, ..., _p__n_ (2 ≤ _p__i_ ≤ 100) in ascending order. The last line gives a single integer _k_ (1 ≤ _k_). It is guaranteed that the _k_\-th smallest integer such that all its prime divisors are in this set does not exceed 1018. ## Output Print a single line featuring the _k_\-th smallest integer. It's guaranteed that the answer doesn't exceed 1018. [samples] ## Note The list of numbers with all prime divisors inside {2, 3, 5} begins as follows: (1, 2, 3, 4, 5, 6, 8, ...) The seventh number in this list (1\-indexed) is eight.

与格里沙的良好表现相反，奥列格虽然有一整年的时间，却未能在去年学会解决数论问题。因此，前来拜访他的不是圣诞老人，而是他的队友安德鲁，安德鲁庄重地送给他一组 #cf_span[n] 个互不相同的质数，并提出一个简单任务：奥列格需要找出第 #cf_span[k] 小的整数，使得该整数的所有质因数都属于这个集合。第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 16]）。第二行按升序列出 #cf_span[n] 个互不相同的质数 #cf_span[p1, p2, ..., pn]（#cf_span[2 ≤ pi ≤ 100]）。最后一行给出一个整数 #cf_span[k]（#cf_span[1 ≤ k]）。保证第 #cf_span[k] 小的、其所有质因数均属于该集合的整数不超过 #cf_span[1018]。请输出一行，包含第 #cf_span[k] 小的整数。保证答案不超过 #cf_span[1018]。所有质因数均属于 #cf_span[{2, 3, 5}] 的数列如下所示： #cf_span[(1, 2, 3, 4, 5, 6, 8, ...)] 该序列中第七个数（#cf_span[1]-索引）是八。 ## Input 第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 16]）。第二行按升序列出 #cf_span[n] 个互不相同的质数 #cf_span[p1, p2, ..., pn]（#cf_span[2 ≤ pi ≤ 100]）。最后一行给出一个整数 #cf_span[k]（#cf_span[1 ≤ k]）。保证第 #cf_span[k] 小的、其所有质因数均属于该集合的整数不超过 #cf_span[1018]。 ## Output 请输出一行，包含第 #cf_span[k] 小的整数。保证答案不超过 #cf_span[1018]。 [samples] ## Note 所有质因数均属于 #cf_span[{2, 3, 5}] 的数列如下所示：#cf_span[(1, 2, 3, 4, 5, 6, 8, ...)]该序列中第七个数（#cf_span[1]-索引）是八。

**Parameters** * $n \in \mathbb{Z}$ such that $1 \le n \le 16$. * $P = \{p_1, p_2, \dots, p_n\}$ is a set of distinct prime numbers where $2 \le p_i \le 100$ for all $i$. * $k \in \mathbb{Z}$ such that $k \ge 1$. **Definitions** Let $S$ be the set of integers generated by the prime basis $P$: $$ S = \left\{ \prod_{i=1}^{n} p_i^{\alpha_i} \;\middle|\; \alpha_i \in \mathbb{Z}_{\ge 0} \right\} $$ Let $(x_j)_{j=1}^{\infty}$ be the sequence of elements of $S$ arranged in strictly ascending order: $$ x_1 < x_2 < x_3 < \dots \quad \text{where } x_j \in S \text{ for all } j $$ **Constraint** $$ x_k \le 10^{18} $$ **Objective** Determine the value of $x_k$.

Samples

Input #1

3
2 3 5
7

Output #1

Input #2

5
3 7 11 13 31
17

Output #2

API Response (JSON)

{
  "problem": {
    "name": "E. Prime Gift",
    "description": {
      "content": "Opposite to Grisha's nice behavior, Oleg, though he has an entire year at his disposal, didn't manage to learn how to solve number theory problems in the past year. That's why instead of Ded Moroz he ",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF912E"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "Opposite to Grisha's nice behavior, Oleg, though he has an entire year at his disposal, didn't manage to learn how to solve number theory problems in the past year. That's why instead of Ded Moroz he ...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "与格里沙的良好表现相反，奥列格虽然有一整年的时间，却未能在去年学会解决数论问题。因此，前来拜访他的不是圣诞老人，而是他的队友安德鲁，安德鲁庄重地送给他一组 #cf_span[n] 个互不相同的质数，并提出一个简单任务：奥列格需要找出第 #cf_span[k] 小的整数，使得该整数的所有质因数都属于这个集合。\n\n第一行包含一个整数 #cf_span[n]（#cf_span[1 ≤ n ≤ 16]）。...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Parameters**\n\n*   $n \\in \\mathbb{Z}$ such that $1 \\le n \\le 16$.\n*   $P = \\{p_1, p_2, \\dots, p_n\\}$ is a set of distinct prime numbers where $2 \\le p_i \\le 100$ for all $i$.\n*   $k \\in \\mathbb{Z}$ s...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments