Как рассчитать наименьшее общее кратное {1, 2, 3, .........., n}?

Как найти LCM {1, 2, ..., n}, где 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;
}

Но этот код не работает так же хорошо. Зачем?

Источник

4 ответа

Решение

Я бы вычислил это совершенно по-другому: LCM {1,...,n} является произведением всех простых чисел p[i]<=n, каждый из которых имеет минимальный уровень мощности (log(n)/log(p[i] ])). Этот продукт делится на все числа до n, и это наименьшее количество. Ваша главная проблема состоит в том, чтобы затем вычислить таблицу простых чисел.

Источник

Ваше текущее решение не является правильным, как уже упоминалось в комментариях.

Одним из способов решения этой проблемы является осознание того, что 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)
}
Источник

Это очень просто, но, кажется, работает достаточно быстро. Вероятно, идея Амит Кумар Гупта быстрее. Переполнение стека вокруг 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));
  }
}
Источник

Я собираюсь предложить что-то менее динамичное, но это значительно увеличит вашу скорость. Установите факториальную таблицу (возможно, массив) и сохраните в ней предварительно рассчитанные факториальные целочисленные представления. Таким образом, это простая операция O(1), а не O(n). Вот справочная таблица, но вы также можете рассчитать их самостоятельно: 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

Источник
Другие вопросы по тегам