1. Идея

Нужно найти минимальное время T, за которое все станки вместе изготовят хотя бы n изделий.

Если время T фиксировано, то легко посчитать, сколько изделий получится:

• i-й станок делает floor(T / t_i) изделий;
• суммарно это sum(floor(T / t_i)).

Заметим важное свойство: если за время T можно произвести хотя бы n изделий, то и за любое большее время тоже можно.
Это означает, что ответ можно искать двоичным поиском по времени.

2. Наблюдения

Наблюдение 1

Для заданного времени T количество произведённых изделий считается независимо для каждого станка:

• станок с временем t_i делает T // t_i изделий.

Тогда суммарное количество:

• produced = T // t_1 + T // t_2 + ... + T // t_m.

Наблюдение 2

Функция "можно ли сделать не менее n изделий за время T" монотонна:

• если ответ "да" для времени T,
• то ответ "да" и для любого T' > T.

Значит, существует граница:

• до неё изделий недостаточно,
• начиная с неё — уже достаточно.

Именно такую границу удобно искать двоичным поиском.

Наблюдение 3

Нужно выбрать хорошие границы поиска.

• Нижняя граница: 0.
• Верхняя граница: min(t) * n.

Почему это корректно:

• самый быстрый станок делает одно изделие за min(t);
• если бы работал только он один, то за min(t) * n он сделал бы ровно n изделий;
• значит, все станки вместе точно успеют не позже этого времени.

3. Алгоритм

1. Считываем m, n и массив t.
2. Находим right = min(t) * n, left = 0.
3. Пока left < right:
   • берём mid = (left + right) // 2;
   • считаем, сколько изделий можно сделать за mid;
   • если изделий хотя бы n, то ответ не больше mid, двигаем right = mid;
   • иначе времени мало, двигаем left = mid + 1.
4. После завершения цикла left и есть минимальное подходящее время.

4. Почему это работает

Докажем корректность.

Пусть check(T) — это утверждение: "за время T можно изготовить не менее n изделий".

1. check(T) вычисляется правильно

Для каждого станка за время T он успевает сделать ровно T // t_i изделий, потому что каждое изделие требует t_i времени.
Сумма по всем станкам даёт точное общее число изделий.

2. Утверждение check(T) монотонно

Если T1 <= T2, то для любого станка:

• T1 // t_i <= T2 // t_i.

Значит, и суммарное число изделий за T2 не меньше, чем за T1.
Следовательно, если за T1 изделий уже хватает, то за T2 тоже хватает.

3. Двоичный поиск находит минимальное подходящее время

Мы ищем минимальное T, для которого check(T) истинно.

• left = 0 — допустимая нижняя граница поиска;
• right = min(t) * n — гарантированно подходящее время.

На каждом шаге:

• если check(mid) истинно, то ответ находится в отрезке [left, mid];
• иначе ответ находится в отрезке [mid + 1, right].

Так как на каждом шаге отрезок уменьшается, поиск завершится.
В момент left == right останется единственное значение, и это минимальное время, за которое можно выполнить заказ.

5. Сложность

Пусть M = min(t) * n.

• Одна проверка времени T требует пройти по всем m станкам: O(m).
• Двоичный поиск делает O(log M) шагов.

Итоговая сложность:

• O(m log M).

Память:

• O(m) на хранение массива t.

6. Код на C++17

Важно: ответ может достигать min(t) * n = 10^9 * 10^18 = 10^27, что не помещается в 64-битный long long (макс. ~9.2 * 10^18). Поэтому границы двоичного поиска, счётчик произведённых изделий и вывод используют __int128.

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>

using namespace std;

static string to_string_i128(__int128 x) {
    if (x == 0) return "0";
    bool neg = x < 0;
    if (neg) x = -x;
    string s;
    while (x > 0) {
        int d = (int)(x % 10);
        s.push_back((char)('0' + d));
        x /= 10;
    }
    if (neg) s.push_back('-');
    reverse(s.begin(), s.end());
    return s;
}

int main() {
    int m;
    long long n;
    cin >> m >> n;

    vector<long long> t(m);
    long long mn = (long long)4e18;
    for (int i = 0; i < m; i++) {
        cin >> t[i];
        mn = min(mn, t[i]);
    }

    __int128 left = 0;
    __int128 right = (__int128)mn * (__int128)n;

    while (left < right) {
        __int128 mid = left + (right - left) / 2;

        __int128 produced = 0;
        for (int i = 0; i < m; i++) {
            produced += mid / t[i];
            if (produced >= (__int128)n) {
                break;
            }
        }

        if (produced >= (__int128)n) {
            right = mid;
        } else {
            left = mid + 1;
        }
    }

    cout << to_string_i128(left) << '\n';
    return 0;
}

7. Код на Python 3

m, n = map(int, input().split())
t = list(map(int, input().split()))

left = 0
right = min(t) * n

while left < right:
    mid = (left + right) // 2

    produced = 0
    for x in t:
        produced += mid // x
        if produced >= n:
            break

    if produced >= n:
        right = mid
    else:
        left = mid + 1

print(left)