a和b之间的数的除数的总和

Question

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

G(A)+ G(A + 1)... +克(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.

有更好的方法吗？

Answer 1

这里有一些简单但相当高效的 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总和。求出 的除数函数之和相当于计算在线整数序列百科全书中的序列 A006218 。该序列相当于从到 的所有整数范围内的总和。ab1bfloor(n / d)d1n

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

评论：

• 该算法有运行时间O(sqrt(b))和恒定的空间要求。运行时间的改进可能会以空间为代价；请参阅上面提到的论文。

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

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