非重复可分红利数(优化)

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中的第一个算法版本

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

一个关键的发现是,在范围[ 甲,乙 ]是非常大的,使得它从望而却步迭代甲到乙.但是,除数列表的大小相对较小.

我们可以在不明确构建相应集合的情况下计算所需数量.

首先,请注意,如果D只包含一个数字(让我们将该数字表示为d),那么我们可以很容易地找到该范围内的倍数:它将是楼层(B/d) - 楼层((A - 1)/ d).问题是当D有多个元素时,简单地将每个元素的上述公式相加会导致多次计算一些数字.

我们可以使用包含 - 排除原则来解决上述问题.

我将用一个小例子说明这种技术: A = 2,B = 8,D = {2,3}.

• 计算有多少数字有2作为除数.有4个这样的数字:{2,4,6,8}.

• 计算有多少数字有3作为除数.有2个这样的数字:{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(2 ^M)子集的代码,其中M是集合D中的最大除数(在当前问题设置中,M = 50).但是,我们可以在评论中使用A. Bau提到的观察来减少D并将子集数量减少到O(2 ^M/2).

如果数字d ₁中d是另一数目的倍数d ₂从d,然后ð ₁具有在最终结果没有影响,我们可以消除它.

在当前问题设置中,D中的所有数字都在{1,2,... 50}中,此预处理可确保我们最多留下25个数字.

我们最多有25个数字这一事实的演示很有意思,但我不会详细介绍(除非有人感兴趣) - 简而言之,我们可以对集合{1,2,...进行分区... 50}到25个不相交的子集中,其中^第 i ^个子集包含形式S _i = {(2∙i-1)∙2 ^k }的数字.选择超过25个数字可以保证我们在同一组中有2个数字,其中较大的数字将除以较小的数字.此外,这个界限很紧,因为我们可以找到不能进一步减少的25个数字的集合,例如{26,27,..,50}.

对于25个数字的最坏情况,我们需要研究2 ²⁵ = 33,554,432个子集,这是可行的,因为可以快速研究每个子集.

以下代码实现了上述想法,并在大型示例中以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(并集(S1,S2))= LCM(LCM(S1),LCM(S2))).

然而,这可能仍然不够,因为即使LCM是即时计算的,当前的方法在我的计算机上仍然需要大约18秒.

最后,我做了另一个实验,我测量了迭代3300万个条目的时间,并在每次迭代期间执行单个整数除法和加法.这在python中大约需要8.4秒,在C++中大约需要0.12秒.

总而言之,本回答中描述的技术可能不是针对给定问题设置的最佳技术,但也可能只是以更快的编程语言实现这些想法符合要求.