5

0 < n < 10001である{1, 2, ..., n}のLCMを可能な限り最速の方法で見つける方法。1 つの方法は、 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

コメントに記載されているように、現在の解決策は正しくありません。

これを解決する 1 つの方法は、これらの数値の最小公倍数は、以下の異なる素数のすべての「最大」累乗の積であることを認識することです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

これは非常に単純ですが、十分に高速に動作するようです。おそらく、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 に答える
0

動的ではないものを提案しますが、速度が劇的に向上します。階乗テーブル (おそらく配列) を設定し、事前に計算された階乗整数表現をそこに格納します。そうすれば、O(n) ではなく、単純な O(1) 操作になります。ここに参照テーブルがありますが、それらを自分で事前に計算することもできます: http://www.tsm-resources.com/alists/fact.html これらの値は変更されないため、そうしても問題ありません。速度の最適化について話している場合は、毎回計算するのではなく、既知の値を保存してみませんか?

ただし、これらの計算を事前に保存することに反対する場合は、最適化されたアルゴリズムを調べて、そこから作業することをお勧めします。

階乗計算アルゴリズムを高速化するための 2 つの優れたリソースを次に示します。

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

于 2015-05-30T08:06:08.843 に答える