algorithm - 正の整数のセットのフロベニウス数を計算するアルゴリズム

Question

セットのフロベニウス数は、セットの数の gcd が 1 である場合に存在します。すべての要素の gcd が 1 であるような最大 10 個の要素を持つ正の整数のセットが与えられた場合、セットのフロベニウス数をどのように計算できますか? ?

元の問題へのリンクは次のとおりです: https://icpcarchive.ecs.baylor.edu/external/62/6298.pdf シルベスターの公式を使用して、2 つの要素のセットのフロベニウス数を見つけることができます。

Answer 1

これにはかなりの数のアルゴリズムがありますが、最適なオプションはおそらく、Bocker と Liptak によるこの 2004 年の論文にあるものです。疑似コードは p968 にありますが、非常に優れた小さなアルゴリズムであるため、論文全体を読む価値があります。