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

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

Но этот код также не работает. Почему?


math greatest-common-divisor lcm
person DCoder    schedule 30.05.2015    source источник
comment
Что означает, что этот код не работает?   -  person B.K.    schedule 30.05.2015
comment
lcm(a, b) * gcd(a, b) = a * b действительно только для двух чисел. Это неправильно для большего количества входных параметров. lcm и gcd имеют разложение на простые множители с максимальным и минимальным показателями соответственно, тогда как произведение их суммирует. И sum(e1, e2, ...) - min(e1, e2, ...) != max(e1, e2, ...).   -  person Nico Schertler    schedule 30.05.2015
comment
Проверьте OEIS, чтобы узнать о вариантах реализации.   -  person Nico Schertler    schedule 30.05.2015
comment
gcd(1,2,...,n) = 1 всегда... это не может быть тем, что вы хотите.   -  person Edward Doolittle    schedule 30.05.2015

Ответы (4)


arrow_upward
2
arrow_downward

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

person begemotv2718    schedule 30.05.2015
comment
Я предлагаю использовать сито Эратосфена для расчета таблицы простых чисел до 10001, это не займет много времени. - person begemotv2718; 30.05.2015

arrow_upward
4
arrow_downward

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

Один из способов решить эту проблему — понять, что НОК этих чисел — это просто произведение всех «самых больших» степеней различных простых чисел, меньших или равных 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)
}
person Amit Kumar Gupta    schedule 30.05.2015

arrow_upward
0
arrow_downward

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

person B.K.    schedule 30.05.2015

arrow_upward
0
arrow_downward

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