计算具有特定lcm属性的素数

这是一个包含-排除问题。您必须了解才能正确执行此操作，因此我将给出完整的解释。

包含-排除的概念看似简单。假设我们要计算满足至少一个k条件的事物的数量。

首先，我们总结出有多少个独立地满足每个条件。

其次，满足2个条件的事物已被计数两次，因此我们减去满足每对条件的事物数。

第三，在第一步中对满足3个条件的事物进行了3次计数，在第二步中减去了3次，并且需要加回来。因此，对于3件事的每种组合，我们添加满足3个条件的总数。

第四，满足4个条件的事物在第一步中被计算了4次，在第二步中被减去了6次，然后在第三步中又被添加了4次，因此被计数了两次。所以减去它。

等等。对于每种i条件组合，我们都将其(-1)^i乘以该组合的数量。

（离题。这是一种方法，它应能起作用。将这个交替的总和作为子集的总和，然后减去并集的数目。如果一个元素在i子集中，则其出现的总和变为是-(i choose 0) * 1（用于减去联合的计数）- (i choose 1) * (-1)（对于每个条件它处于的条件）- (i choose 2) * (-1)^2（对于每对条件），依此类推。这是一个总和，归结为- (1 - 1)^i = 0。因此，这个交替的总和减去联合的计数为0 。这意味着交替总和必须是联合的计数。离题。）

现在看来，计算2^k满足条件组合的条件似乎不是找到满足条件的条件的好方法k。但是通常是这样。特别是在数论问题中，其中每个条件都涉及一个质数的可除性，并且“满足条件的组合”等同于“除以数”。如果我们只能在一定范围内被数字整除，那么条件组合的数量可能非常合理。被这些数字整除的事物的数量也下降了。

实际上，这是如此之多，以至于数学家创建了一个特殊的函数（μ又名Möbius函数）来描述在包含/排除运算中应将数字包含+，-还是完全忽略。

理论足够多，在这里如何应用？在您的问题中，每个M_i都有一个相关的编号n_i = (M_i - 1) / 2。您的最后一个条件归结为说您想选择一组M_i相关的n_i元素是相对质数的。这意味着您要：

count of sets of j of your possible M_i
  - counts of sets of j of your possible M_i
    such that 2+ of the associated n_i are divisible by some prime

所以，首先生成您的查找表和把它变成一个位向量(M_min-1)/2来(M_max-1)/2的关联n_i。

我们可以很容易地获得第一个计数-让其k成为计数，然后就(k choose j)得到它们。

第二个计数需要包含-排除。对于每个nin，2..(M_max-M_min)/2您都可以计算出矢量中被1整除的方式是1的方式n。如果j大于等于2，则计算出向量中有2+个元素可被整除的事物集n。将该数值乘以，μ(n)它便成为您总和的一部分。

现在的诀窍是这个。如果N位向量的长度是，则n访问量很小，但是n访问量越大，访问量就越少。实际上，如果N/2 < n您最多只访问2个元素。即使计算看起来很吓人，您仍然只需要O(N log(n))在位向量中查找即可生成O(N)项。并且计算出Möbius函数N也需要O(N log(N))工作。

因此，除了您已经完成的工作外，其余算法是O(N log(N))。

祝好运！