如何计算{1, 2, 3, ......., n}的最小公倍数？

Question

如何找到 LCM of {1, 2, ..., n} where 0 < n < 10001 以最快的方式。一种方法是计算 n! / gcd (1,2,......,n) 但这可能会很慢，因为 测试用例 的数量 t < 501 并且输出应该是 LCM ( n! ) % 1000000007

代码同样是：

#include<bits/stdc++.h>
using namespace std;
#define p 1000000007;
int fact[10001] = {1};
int gcd[10001] = {1};

int main()
{
    int i, j;
    for( i = 2;i < 10001; i++){
        fact[i] = ( i * fact[i-1]) % p;
    }
    for(i=2 ;i < 10001; i++){
        gcd[i] =__gcd( gcd[i-1], i );
    }

    int t;
    cin >> t;

    while( t-- ) {
        int n;
        cin >> n;
        int res = ( fact[n] / gcd[n] );
        cout << res << endl;
    }

    return 0;
}

但此代码的性能不佳。为什么？

Answer 1

我将建议一些不太动态的东西，但它会显着提高你的速度。设置一个阶乘 table （可能是一个数组）并在那里存储预先计算的阶乘整数表示。这样，它就是一个简单的 O(1) 操作，而不是 O(n)。这是参考 table，但您也可以自己预先计算：http://www.tsm-resources.com/alists/fact.html 这样做没关系，因为这些值永远不会改变。如果我们谈论速度优化，那么为什么不存储我们知道的值，而不是每次都计算它们？

但是，如果您反对预先存储这些计算结果，我建议您查看优化算法并从那里开始工作：

这里有两个关于更快的阶乘计算算法的优秀资源：

http://www.luschny.de/math/factorial/conclusions.html http://www.luschny.de/math/factorial/scala/FactorialScalaCsharp.htm

Answer 2

我会用完全不同的方式计算它：{1,...,n} 的 LCM 是所有素数 p[i]<=n 的乘积，每个素数都在 power floor(log(n)/日志（p[i]））。这个乘积可以被所有数字整除，直到 n，这是最小的数字。你的主要麻烦是计算 table 个素数。

Answer 3

如评论中所述，您当前的解决方案不正确。

解决这个问题的一种方法是认识到这些数字的 LCM 只是小于或等于 n 的不同素数的所有 "largest" 次幂的乘积。也就是说，找到每个小于或等于 n 的素数 p，然后找到每个素数的最大幂，使其仍然小于或等于 n，然后将它们相乘一起。对于给定的 p，所述幂可以用伪代码表示为：

p ** math.Floor(math.Log(n) / math.Log(p))

这是 Golang 中的一个实现 returns 立即：

http://play.golang.org/p/8s4eE_CQ9Y

$ time go run lcm.go
5793339670287642968692270879166240098634860297998518825393138351148979300145773182308832598
<several lines later>
800000

real    0m0.225s
user    0m0.173s
sys     0m0.044s

为了完整起见，此处粘贴了来自 playground link 的完整代码：

package main

import (
    "fmt"
    "math"
    "math/big"
)

func main() {
    n := 10001

    primes := make([]int, 1, n)
    primes[0] = 2

SIEVE:
    for i := 3; i <= n; i++ {
        for _, p := range primes {
            if i%p == 0 {
                continue SIEVE
            }
        }
        primes = append(primes, i)
    }

    logN := math.Log(float64(n))
    lcm := big.NewInt(1)
    for _, p := range primes {
        floatP := float64(p)
        e := math.Floor(logN / math.Log(floatP))
        lcm.Mul(lcm, big.NewInt(int64(math.Pow(floatP, e))))
    }

    fmt.Println(lcm)
}

Answer 4

这很简单，但似乎运行不够快。可能 Amit Kumar Gupta 的想法更快。在我的机器上，堆栈溢出在 n = 9500 左右，但这可以通过记忆函数并从小数到大数构建备忘录来解决。我没有采用模数，但修复很容易，特别是如果模数是素数。是吗？

import java.math.BigInteger;

public class LCM {

  // compute f(n) = lcm(1,...n)
  public static BigInteger f(int n) {
    if (n == 1) return BigInteger.ONE;
    BigInteger prev = f(n-1);
    return prev.divide(prev.gcd(BigInteger.valueOf(n)))
      .multiply(BigInteger.valueOf(n));
  }

  public static void main(String[] args) {
    int n = Integer.parseInt(args[0]);
    System.out.println("f(" + n + ") = " + f(n));
  }
}

如何计算{1, 2, 3, ......., n}的最小公倍数？

How to calculate Least common multiple of {1, 2, 3, .........., n}?

math

lcm

greatest-common-divisor