与えられた数kとソートされた数のセット。この数を分割する数がセットにあるかどうかを調べます。
たとえば、k = 8で、セットが{3、4、5}の場合、4は8を除算します。4が答えです。
最悪の場合の解決策はO（n）です。
もっと上手くできますか？
3 に答える
2
数を因数分解して (8 は 4 2 1 になります)、与えられたセットで因数を検索してみてはどうでしょうか? 交点集合または二分探索を因子のリストで使用できます。大規模なセットの場合は、より迅速な回答が得られると思います。
于 2011-03-01T09:46:39.357 に答える
0
k の gcd とセットのメンバーの積を計算します。たとえば、gcd(3*4*5,8) = 4 です。
于 2011-09-26T13:07:26.723 に答える
0
k が素数の場合、集合に因数がなく、完了です。それ以外の場合、k = p*q です。ここで、p は k の最小係数です。q の二分探索を行います。見つかったら完了です。それ以外の場合は、k=p'*q' をリファクタリングします。ここで、p' は p の次に大きい k の因数です。何もなければ、完了です。それ以外の場合は、q' のバイナリ検索を続行します。q' < q であるため、q に使用される上限を使用して検索を続行できます。因数が見つかるか、k の最大の因数を検索するまで続けます。これがO(logn)です。k = 8 の具体的なケースでは、最初に 4 を検索し、次に 2 を検索します...どちらも見つからない場合、セットには k の約数が含まれていません。
編集:うーん...これはO(logn)ではないと思います。たとえば、リストに k の因数 f ごとに f-1 が含まれている場合、各 f を連続して検索し、毎回 f-1 をヒットする必要があります...それは O(n) になります。
于 2011-03-01T10:31:57.633 に答える