求出(N!)^ 2的除数

Question

我试图解决以下问题,我将其简化为: 找到(N!)^ 2的除数

我编写了我的解决方案,我在这里作为答案包含在内(因为没有被指责不做任何工作),并且即使是大数字也能正常快速地工作,但因为它没有通过所有的测试超时,我认为我的算法效率不高.

这是我的想法的概述:

1. 任何数字都可以表示为a0^b1*a1^b1*...*an^bn具有(1 + b1)*(1 + b2)*...*(1 + bn)除数
2. 然后M^2将有(1 + 2b1)*(1 + 2b2)*...*(1 + 2bn)除数
3. 创建一个函数,查找数字的所有因子并将它们保存为hashmap
4. 有一个函数,它将通过添加相应键的值来组合两个哈希映射
5. 使用这两个函数迭代从2到n的所有数字,得到所有阶乘的除数
6. 使用1.中的函数来得到答案

我认为这个解决方案非常有效,但看起来有更好的方法.谁能建议我一个更好的方法？

Answer 1

您的问题有一个简单有效的解决方案.注意n!是:

1 * 2 * 3 * 4 * 5 * 6 * 7 * 8 * ... * n

例如,让我们考虑一下这个产品中出现一个主要因素的次数2.每个2因素都会出现一次.但是,一旦每个4因素出现两次.并且一旦每个8因素出现三次等等.换句话说,因子2将出现在n! sum(n//(2**e) for e in range(1, n))时间中.任何素因子都是如此k.

您可以使用以下方法实现此计算

import itertools as it

def exp_for_factor_in_factorial(factor, n):
    total = 0
    for e in it.count(1):
        if factor ** e > n:
            break
        total += n // factor**e
    return total

现在,为了找到n!我们需要找到所有素数的所有素因子n,这很容易使用eratosthenes:

import math

def sieve(n):
    nums = [True] * (n+1)
    nums[:2] = [False]*2
    nums[4::2] = [False] * math.ceil((n-3)/2)
    for i in range(3, int((n+1)**.5)+1, 2):
        if nums[i]:
            for j in range(i*i, n+1, 2*i):
                nums[j] = False
    return [i for i,k in enumerate(nums) if k]

这使我们可以获得以下因子分解n!:

def get_factorization_factorial(n):
    primes = sieve(n)
    factors = []
    for p in primes:
        factors.append((p, exp_for_factor_in_factorial(p, n)))
    return factors

最后,要计算分解中除数的数量,可以使用已经提到的公式:

import operator as op
from functools import reduce

def get_num_divisors(factorization):
    return reduce(op.mul, (e+1 for _, e in factorization), 1)

因此最终答案可以通过以下方式获得:

def divs_of_squared_fact(n):
    return get_num_divisors((p, 2*e) for p, e in get_factorization_factorial(n))

请注意,此解决方案比您的解决方案性能更高:

In [41]: %%timeit
    ...: for i in range(2, 1000):
    ...:     x = divs_of_squared_fact(i)
    ...: 
1 loops, best of 3: 276 ms per loop

In [42]: %%timeit
    ...: for i in range(2, 1000):
    ...:     x = divisorsOfFactorialSquare(i)
    ...: 
1 loops, best of 3: 7.89 s per loop

它能够产生(5000!)^2大约的除数2ms,而另一个则需要几乎半秒:

In [47]: %timeit divs_of_squared_fact(5000)
100 loops, best of 3: 2.07 ms per loop

In [48]: %timeit divisorsOfFactorialSquare(5000)
1 loops, best of 3: 439 ms per loop

嗯,实际上答案具有不同的渐近复杂度,因此在增加参数时差异会变为无穷大.