需要帮助在时间复杂度方面有效地解决以下问题

Question

最近两天我正在尝试解决以下问题。除了蛮力，我想不出任何解决方案。任何类型的提示或参考将不胜感激。 TIA.

"Given N distinct prime integers i.e p1, p2,..., pN and an interval [L,R]. Calculate the number of integers in this interval that are divisible by at least one of the given primes."

N 很小 (1<=N<=10) 而 L,R 很大 (1<=L<=R<=10^10)

Answer 1

假设 n 是区间大小，N 是常量。

对于每个素数 p，在可被素数整除的区间内应该大致有 (R-L) / p 个数。

找到区间内第一个可被 p 整除的数：L' = L + (p - L % p)。

现在如果L' > R，则有none；否则有 1 + floor((R-L') / p).

示例：3、[10、20]：

L' = 10 + 3 - 10 % 3 = 12。

区间内可被 3 整除的数字：1 + floor((20 - 12) / 3) = 3

注意：到目前为止，我们还没有使用 p1..pN 是素数这一事实。

剩下的问题似乎是：如何避免多次计算一个可被多个质数整除的数？示例：假设我们有 3,5 和 [10, 20]，我们需要避免将 15 计数两次...

也许我们可以使用上面的计数算法来计算除以(p1*p2)等的可除性，并相应地减少总数？如果 N 是 const，这应该仍然是 const 时间。因为 p1...pN 是素数，所以它们的所有乘积都必须不同（因为任何数字都不能有超过一个素数分解）。

Answer 2

首先注意，限制问题更容易，忽略下界（即：对待L=1）。如果我们可以计算被素数整除的数字 <= N 对于任何 N，我们也可以通过从计数 <= R.

中减去数字 <= L-1 的计数来计算它们的间隔

给定任何数字 x，数字 <= R 可被 x 整除的计数是 floor(R / x)。

现在，我们可以应用 inclusion-exclusion principle 来获得结果。首先，我将手写3个素数p1、p2和p3的结果，然后给出一般结果。

<= R 可被 p1、p2 或 p3 整除的数字的个数是：

R / p1 + R / p2 + R / p3
- R / (p1p2) - R / (p1p3) - R / (p2p3)
+ R / (p1p2p3)

（这里假设/是整数除法）

一般情况如下：

sum((-1)^(|S|+1) * R / prod(S) for S a non-empty subset of {p1, p2, .., pN}).

这里S范围遍及你的质数的所有子集，prod(S)是子集中质数的乘积，初始项根据大小在-1和+1之间变化子集。

对于你的问题，N<=10，所以有 1023 个非空子集，其中有少量要迭代的东西。

下面是一些示例 Python 代码：

from itertools import *

def powerset(iterable):
    s = list(iterable)
    return chain.from_iterable(combinations(s, r) for r in range(len(s)+1))

def prod(ns):
    r = 1
    for n in ns:
        r *= n
    return r

def divs(primes, N):
    r = 0
    for S in powerset(primes):
        if not S: continue
        sign = 1 if len(S) % 2 else -1
        r += sign * (N // prod(S))
    return r

def divs_in_range(primes, L, R):
    return divs(primes, R) - divs(primes, L-1)

请注意，此代码的运行时间或多或少仅取决于素数的数量，而不是 L 和 R 的大小。

需要帮助在时间复杂度方面有效地解决以下问题

Need help in solving the following efficiently in terms of time complexity

algorithm

performance

complexity-theory