Codeforces Round 456 (Div. 2) |
---|
Закончено |
— Нету.
— На, мужик, простые числа.
В отличие от Гриши, который вел себя хорошо, Олег за весь год так и не научился решать задачи на теорию чисел. Поэтому вместо Деда Мороза к нему пришел его сокомандник Андрей и торжественно вручил ему множество из n различных простых чисел вместе с простой задачей: Олегу необходимо найти k-е в порядке возрастания положительное целое число, среди простых делителей которого встречаются числа только из этого множества.
В первой строке задано целое число n (1 ≤ n ≤ 16) — количество чисел во множестве.
Во второй строке n различных простых чисел p1, p2, ..., pn (2 ≤ pi ≤ 100) — числа во множестве. Гарантируется, что числа идут в порядке возрастания.
В третьей строке задано число k (1 ≤ k). Гарантируется, что k-е в порядке возрастания положительное целое число, среди простых делителей которого встречаются числа только из данного множества не превосходит 1018.
Выведите k-е в порядке возрастания число, удовлетворяющее условию. Гарантируется, что оно не превосходит 1018.
3
2 3 5
7
8
5
3 7 11 13 31
17
93
Для первого примера последовательность с простыми делителями из набора {2, 3, 5} выглядит так:
(1, 2, 3, 4, 5, 6, 8, ...)
Седьмым по счету числом (в 1-индексации) как раз и будет восьмерка.
Название |
---|