Алгоритмы вычисления чисел Фробениуса из набора натуральных чисел

Question

Числа Фробениуса набора существуют тогда и только тогда, когда gcd номеров набора равен 1. Если набор положительных целых чисел состоит не более чем из 10 элементов, так что gcd всех элементов равен 1, как мы можем вычислить число Фробениуса набора?

Вот ссылка на исходную задачу: https://icpcarchive.ecs.baylor.edu/external/62/6298.pdf помощью формулы Сильвестра можно найти число Фробениуса для набора из 2 элементов.

Answer 1

Для этого есть немало алгоритмов, но лучшим вариантом для вас, вероятно, является тот, который представлен в работе 2004 года Бокером и Липтаком. Псевдокод можно найти на p968, хотя его стоит прочитать, потому что это довольно аккуратный маленький алгоритм.