5

如何以最快的方式找到0 < n < 10001的{1, 2, ..., n}的LCM 。一种方法是计算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;
}

但是这段代码表现不佳。为什么？

4

4 回答 4

4

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

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

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

这是立即返回的 Golang 实现：

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

为了完整起见，该游乐场链接的完整代码粘贴在这里：

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)
}
于 2015-05-30T08:56:49.653 回答
2

我会以完全不同的方式计算这个：{1,...,n} 的 LCM 是所有素数 p[i]<=n 的乘积，每个素数都在幂层(log(n)/log(p[i ]))。这个产品可以被所有直到 n 的数整除，这是最小的数。你的主要麻烦是计算素数表。

于 2015-05-30T08:21:45.780 回答
0

我将建议一些不那么动态的东西，但它会大大提高你的速度。设置一个阶乘表（可能是一个数组）并在那里存储预先计算的阶乘整数表示。这样，与 O(n) 相比，这是一个简单的 O(1) 操作。这是一个参考表，但您也可以自己预先计算：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

于 2015-05-30T08:06:08.843 回答
0

这很简单，但似乎运行得足够快。可能 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));
  }
}
于 2015-05-30T09:24:19.093 回答