python - 非重复可分红数(优化)

Question

有没有办法改进我的算法，使其在计算时间方面达到最优？
给定一个非零红利数[a，b]（1<=a，b<=10^18）的范围和一组除数d={x:1<=x<=50}，我想找出[a，b]中的非重复红利的总数，它可以除以集合d中的任何数。
例1（不需要太多时间）
被除数的范围[1,10]和除数的范围{2,3,4}
除数2的可除数列表：2,4,6,8,10
除数3的可除数列表：3,6,9
除数4的可除数列表：4,8
因此，在[1,10] = 7中，不可重复可分红利的总数
例2（需要很多时间）

[A,B] = [79031836253224256, 403892407826392155]
D = {44, 46, 50, 8, 35,41,6,18, 24, 23, 7, 45, 39, 46, 4, 35, 34}
Output: 161802330522861274

Python算法的第1个版本

def solution(A,B,D):                                                                                                                                                                         
    a = set()                                                                                                      
    for i in range(A,B+1):                                                                                         
            for j in D:                                                                                            
                    if i%j == 0:                                                                                   
                            a.add(i)                                                                               
    # return the count of a                                                                                        
    return len(a)   

if __name__ == "__main__":                                                                                             
        print(solution(1,10,[2,3,4]))                                                                                  

Answer 1

一个关键的观察结果是，范围[a，b]非常大，使得从a到b的迭代变得非常困难。然而，除数列表的大小相对较小。
我们可以在不显式构造相应集合的情况下计算所需的数目。
首先，请注意，如果D只包含一个数字（让我们将该数字表示为D），那么我们可以很容易地找到该范围内的倍数：它是floor（B/D）-floor（（a-1）/D）问题是，当D有多个元素时，简单地对每个元素的上述公式求和将导致多次计算某些数字。
我们可以使用inclusion-exclusion principle来解决上述问题。
我将用一个小例子来说明这一技术：
A=2，B=8，D={2，3}。
数一数有多少个数有2作为除数有4个这样的数字：{2，4，6，8}。
数一数有多少个数有3作为除数有两个这样的数字：{3，6}。
数一数有多少个数同时有2和3作为除数只有一个这样的号码：{6}。
根据包含排除原理，要计算多少个数在给定集合中至少有一个除数，我们需要将步骤1和2的结果相加，然后从步骤3中减去结果（这是因为在步骤1和2中，我们已经对数字6进行了两次计数）。因此，结果是4+2-1=5。
一般来说，我们需要考虑集合d的所有子集。对于每个子集，我们需要计算[a，b]范围内有多少个数可以被当前子集中的所有数整除。这个数字等于floor（b/lcm）-floor（（a-1）/lcm），其中lcm是当前子集中所有数字的最小公倍数。
预处理除数列表。
上述思想的直接实现导致了一个研究O（2M）子集的代码，其中M是集合D中的除数的最大数目（在当前问题设置中，M＝50）。然而，我们可以使用A.Bau在评论中提到的观察来减少D，并将子集的数量减少到O（2M/2）。
如果d中的一个数d1是d中另一个数d2的倍数，则d1对最终结果没有影响，我们可以消除它。
在当前的问题设置中，D中的所有数字都在{1，250}，这个预处理保证我们最多只剩下25个数字。
我们最多有25个数字的演示很有趣，但我不会详细讨论（除非有人感兴趣）--简而言之，我们可以划分集合{1，2，……50}分成25个不相交子集，其中ith子集包含si={（2∙i-1）∙2k}形式的数字。选择25个以上的数字可以保证在同一个集合中有2个数字，其中较大的数字将除以较小的数字。而且，这个界是紧的，因为我们可以找到25个数的集合，它们不能再减少了，例如{26，27，…，50}。
对于25个数的最坏情况，我们需要研究225=33554432个子集，这是可行的，因为每个子集都可以被快速地研究。
下面的代码实现了上述思想，并在0.002秒内运行（对于大型示例）：

import itertools
import time


def gcd2(a,b):
    while b > 0:
        a, b = b, a % b

    return a


def lcm2(a, b):
    return int(a * b / gcd2(a, b))


def lcm(list):
    ans = list[0]

    for i in range(1, len(list)):
        ans = lcm2(ans, list[i])

    return ans


def preprocess(D):
    D2 = []
    D = sorted(D)

    for i in range(len(D)):
        include = True
        for j in range(i):
            if D[i] % D[j] == 0:
                include = False
                break

        if include:
            D2.append(D[i])

    return D2


def solution2(A, B, D):
    D = preprocess(D)

    ans = 0
    for num in range(1, len(D) + 1):
        for list in itertools.combinations(D, num):
            v = lcm(list)

            sign = 1 if len(list) % 2 == 1 else -1
            val = sign * ((B // v) - (A - 1) // v)
            ans += val

    return ans


if __name__ == '__main__':
    [A, B] = [79031836253224256, 403892407826392155]
    D = [44, 46, 50, 8, 35, 41, 6, 18, 24, 23, 7, 45, 39, 46, 4, 35, 34]

    t = time.time()
    print(solution2(A, B, D))
    print('processing took {} s. '.format(time.time() - t))

结果是：

161802330522861274
processing took 0.00200653076171875 s. 

讨论。
正如评论中所指出的，在最坏的情况下，这仍然需要很长的时间，包括除数集{26，27，…，50}。在我的电脑上大约需要6分钟。
在这种情况下，需要考虑大约3300万个子集，并且需要为每个此类子集计算最小公倍数（LCM）。
现在，lcm计算是为每个子集单独进行的，但是可以共享一些计算（因为lcm（union（s1，s2））=lcm（lcm（s1，s2）））。
尽管如此，这可能仍然不够，因为即使lcm是即时计算的，当前的方法在我的计算机上仍需要大约18秒。
最后，我做了另一个实验，我测量了遍历3300万个条目的时间，并在每次迭代中执行一个整数除法和一个加法。在Python中大约需要8.4秒，C++中大约需要0.12秒。
总之，本答案中描述的技术可能不适合给定的问题设置，但也有可能仅用更快的编程语言实现这些思想就符合要求。