7

假设有一个函数g(x)=x 的除数个数。给定两个整数 a 和 b 我们需要找到->

g(a)+g(a+1)....+g(b)。

我以为这一步->

for every x from a to b

sum+=number of divisor of x(in sqrt(x) complexity)

但它给定的1<=a<=b<=2^31-1

因此，在 a 和 b 之间进行迭代可能会花费我很多时间......例如->如果 a=1 和 b=2^31-1。

有更好的方法吗？

4

5 回答 5

4

这里有一些简单但相当有效的 Python 代码来完成这项工作。

import math

def T(n):
    "Return sum_{i=1}^n d(i), where d(i) is the number of divisors of i."
    f = int(math.floor(math.sqrt(n)))
    return 2 * sum(n // x for x in range(1, f+1)) - f**2

def count_divisors(a, b):
    "Return sum_{i=a}^b d(i), where d(i) is the number of divisors of i."
    return T(b) - T(a-1)

说明： 能够计算 到 的和就足够了1，b然后我们可以做两个单独的计算并减去以得到 到 的a和b。从整数序列的在线百科全书中找到除数函数的1和相当于b计算序列A006218。该序列等价于从到的所有整数的floor(n / d)asd范围之和。1n

现在该序列可以被认为是双曲线下的整数值点的数量xy=n。我们可以利用双曲线绕线的对称性，用和 来x = y计算整数点。最终会重复计算两个和小于的点，所以我们减去的平方来补偿。所有这些都在本文的介绍中（简要地）解释了。x <= sqrt(n)y <= sqrt(n)xysqrt(n)floor(sqrt(n))

评论：

  • 该算法具有运行时间O(sqrt(b))和恒定的空间要求。以牺牲空间为代价，可以提高运行时间；见上面提到的论文。

  • 对于非常大n的 ，您需要一个适当的整数平方根而不是使用floor(math.sqrt(n))，以避免浮点不准确的问题。这不是n您正在查看的那种问题。使用典型的 IEEE 754 浮点和正确舍入的平方根运算，在n超过2**52.

  • 如果a和b真的很接近，可能会有更有效的解决方案。

于 2013-10-15T17:12:53.903 回答
1
于 2013-10-15T16:25:41.213 回答
0

另一个基于筛的答案，但比其他答案具有更好的时间复杂度。这也很容易处理分割，因为它只{a...b}在每次运行时筛选数字。该函数返回 a ，其中包含从到int[]的每个数字的除数。只需将它们汇总即可获得最终答案。ab

如果您的输入较大，您可以将其拆分并添加每个返回段的总和。

爪哇：

public static int[] getDivisorCount(int a, int b){
    int[] sieve = new int[b - a + 1];
    double max = Math.ceil(Math.sqrt(b));
    for(int i = 1; i <= max; i++){
        int j = (a / i) * i;
        if(j < a)
            j += i;
        for( ; j <= b; j += i){
            double root = Math.sqrt(j);
            if(i < root){
                sieve[j - a] += 2;
            }else if(i == root){
                sieve[j - a]++;
            }
        }
    }
    return sieve;
}

外循环运行sqrt(b)次数。内部循环运行类似log(b-a)时间，所以除非我弄错了，否则最终的复杂性应该是类似的O(sqrt(b) * log(b))，因为最坏的情况是a=1. 请随时纠正我。

如果您正在处理大量输入并且您有足够的空间，您可能需要考虑预先填充一个sqrt表以使其脱离内部循环。它会加快速度，如果你有多余的内存，它没有真正的缺点。

为了快速测试，这里有一个 ideone.com 示例。

编辑：如果您正在寻找筛子，这很好。但是，我必须说jwpat7 的答案是 1）更快，2）恒定空间，3）更优雅（IMO）。除非你对它的机制感兴趣，否则基本上没有理由使用筛子。

于 2013-10-15T16:19:22.187 回答
0

我们可以调整这个算法：http ://en.wikipedia.org/wiki/Sieve_of_Eratosthenes 通过将所有倍数加 1 而不是将它们标记为“非素数”

它将是 o(n.ln(n)) 与 a=1 和 b=n （我认为）

1到n的算法：

g: array of n elements
for i starting with 2 to n
    if g[i]== 0
        for each multiple of i <n
            g[i] += 1
于 2013-10-15T13:04:46.777 回答
0

您可以筛选除数的数量，然后将计数相加：

function divCount(a,b)
    num := makeArray(1..b, 0)
    for i from 1 to b
        for j from i to b step i
            num[j] := num[j] + 1
    sum := 0
    for i from a to b
        sum := sum + num[i]
    return sum

这类似于埃拉托色尼筛法，但不是标记复合数，而是计算每个数字的每个除数，包括素数和复合数。如果b太大，可以分段筛分。

于 2013-10-15T13:09:48.327 回答