N（N <= 100000）要素a1、a2、....、anの配列を想定し、その中に範囲が与えられますL、Rここで、1 <= L <= R <= N、数を取得する必要があります与えられたセットSから少なくとも1つの数で割り切れる、与えられた範囲内の値の場合、このセットは{1,2、....、10}の任意のサブセットにすることができます。複数の範囲と複数のSを要求する可能性があるため（多くのクエリQ、Q <= 100000）、高速な方法を使用する必要があります。そのため、毎回値をループするのは非常に遅くなります。
それぞれN個の要素の10個の配列に大きなセット{1,2、....、10}の各数値で割り切れる値の数を格納し、累積合計を行って特定の数値で割り切れる値の数を取得することを考えましたO（1）時間の任意の範囲で、たとえば、次の少なくとも1つで割り切れる値の数を取得する必要がある場合：2、3、5、次に、それぞれで割り切れる値の数を加算してから削除します。交差点ですが、毎回2 ^ 10または2 ^ 9の計算を行わずに交差点を計算する方法を適切に理解していませんでした。これも、100000回実行される可能性があるため、非常に遅くなります（おそらくメモリを大幅に消費します）。 ？
あなたの考えは正しいです。包除原理と接頭辞の合計を使用して、答えを見つけることができます。あなたがする必要があるもう一つの観察があります。
数字のペアがaありb、a除算するようなセットにある場合、クエリへの回答を変更せずにb削除できbます（実際、、の場合）。したがって、要素が他の要素を分割しないようなセットを常に取得します。b | xa | x
そのようなマスクの数は2^10。よりも少ないです。実際、それは102です。これを計算するコードは次のとおりです。
def good(mask):
for i in filter(lambda b: mask & (1 << (b - 1)), range(1, 11)):
if (any(i % j == 0 for j in filter(lambda b: mask & (1 << (b - 1)), range(1, i)))):
return False
return True
print(list(filter(good, range(1, 2 ** 10)))))
したがって、前処理には100N、保存するためのおおよその操作と数が必要です（かなり小さいように見えます）。
さらに、5「適切な」マスクにはほとんどの要素があります（上記のコードを使用して確認できます）。したがって、around2^5操作を使用して各クエリに答えることができます。
この記事はインターネットから収集されたものであり、転載の際にはソースを示してください。
侵害の場合は、連絡してください[email protected]
コメントを追加