计算从1到k的lcm(i,j)、i和j之和的最有效方法是什么？

html5 • • 问答

问题 ：

我的解决方案：

该解决方案有效，但不幸的是，当k很大时它真的太慢了（例如，k 可以是与 69533550916004 一样大的数字）

var k = 14;
var res = 0;
for(let i = 1; i <= k; i++){
  for(let j = 1; j <= k; j++){
    res += lcm(i, j);
  }
}
console.log(res)

function lcm(a,b){
  return (a * b) / gcd(a,b);
}

function gcd(a,b){
  if(!b){
    return a; 
  }  
  return gcd(b, a % b); 
}

回答

这是一个很大的值k——二次时间是行不通的。这是一个O(k log log k)时间算法，与埃拉托色尼筛法相同。

首先，一些数论。我们知道lcm(i, j) = (i*j) / gcd(i, j)。如果我们试图评估

 k   k
sum sum (i*j),
i=1 j=1

那么我们可以使用分配律重写：

 k   k            k    2
sum sum (i*j) = (sum i)  = ((k+1)*k / 2)^2.
i=1 j=1          i=1

我们可以尝试通过总结可能的最大公约数来挽救这个想法g：

 k   k                k         [k/g]      2
sum sum lcm(i, j) =? sum (1/g)*( sum  (g*i) ),
i=1 j=1              g=1         i=1

但当然这是错误的，因为我们最终（例如）lcm(2, 2)被表示两次，一次是g=1，一次是g=2。为了解决这个问题，我们转向莫比乌斯反演，它给了我们正确的公式

 k   k               k                [k/g]      2
sum sum lcm(i, j) = sum f(g)*(1/g)*( sum  (g*i) ),
i=1 j=1             g=1                i=1

                     k                              2
                  = sum g*f(g)*(([k/g]+1)*[k/g] / 2) ,
                    g=1

其中的定义f(g)是

f(g) =  product  (1-p).
       prime p|g

我们可以f通过修改 Eratosthenes 的筛子来批量评估。下面的 Python 3：

def fast_method(k):
    f = [1] * (k + 1)
    for i in range(2, k + 1):
        if f[i] != 1:
            continue
        for j in range(i, k + 1, i):
            f[j] *= 1 - i
    return sum(g * f[g] * ((k // g + 1) * (k // g) // 2) ** 2 for g in range(1, k + 1))


import math


def slow_method(k):
    return sum(math.lcm(i, j) for i in range(1, k + 1) for j in range(k + 1))


def test():
    for k in range(100):
        assert fast_method(k) == slow_method(k), k


test()

以上是计算从1到k的lcm(i,j)、i和j之和的最有效方法是什么？的全部内容。
THE END
分享
二维码
< <上一篇
下一篇>>
相关内容