TooNewbie's blog

LCM of first N numbers
By TooNewbie, history, 7 years ago, In English

Have to find LCM of first N numbers where N<=1000. Help me please

  • Vote: I like it
  • +9
  • Vote: I do not like it

Comments Comments (14)
| Write comment?
»
7 years ago, # |
← Rev. 3   Vote: I like it +5 Vote: I do not like it

lcm(a, b) = a * b / gcd(a, b)

lcm(a, b, c) = lcm(lcm(a, b), c)

→ Reply
»
7 years ago, # |
← Rev. 3   Vote: I like it +1 Vote: I do not like it

Sieve for all prime numbers: O(N logN)

Calculate the multiple result of all prime numbers to the power which does not exceed N: O(N/logN * logN) = O(N)

You can only consider 512*729*625... since it includes all the prime number combination that you will take for <1000.

→ Reply
»
7 years ago, # |
← Rev. 2   Vote: I like it +6 Vote: I do not like it

Any hints on how to solve the same problem for harder constraints?

See this problem

Update : Here is my implementation using the method told by Morass below. It passes in 1.38 second with cin/cout with any ios::base optimisations. Using fastio, the code passed in 1.25 seconds;

→ Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it +3 Vote: I do not like it

    Good day to you!

    I guess it is not optimal approach, yet it got AC:

    At first, generate all primes <= 10^8. If you have "good sieve" , you can do this easily under one second.

    The get all queries and sort them (so — lets do this offline)

    Now let us have two pointers: One on a number, second on "query". Let us also have some answer and some "set with TODO-list"

    Now some events might occur:

    1. The number is greater than actual query: In this case, update actual query and move with query pointer

    2. The first element of TODO-list is equal to number: Multiply answer by the value stored in TODO-list

    3. The Number is not prime: Skip it

    4. The number is prime: Multiply answer with it and add all its powers to TODO-list

    There above points shall be processed in given order.

    Lastly print all queries.

    Hope it is understandable, if not then don't hesitate to ask more.

    Here is mine solution.

    Good Luck & Have nice day! :)

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it +5 Vote: I do not like it

      Thank you, the method is quite understandable and easy to implement.

      → Reply
  • »
    »
    7 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    using the same formula which CodeItLikeAidos wrote. The problem that you need to find the result of division by modulo M. For this you just need to calculate a^{m-2} mod m. It is easy to calculate this in log time.

    lcm(a, b) =( a * b * gcd(a, b) * a^(m-2)) mod m

    → Reply
    • »
      »
      »
      7 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      Can you briefly a bit more about the method as it is unclear to me as of now?

      Also, lcm(a, b, c) = lcm((lcm(a, b), c) for which you require gcd(lcm(a, b), c) as per Erumaru's comment, but it will become difficult to calculate as the number of numbers become very large. Correct me, if I am wrong/mistaken here?

      → Reply
    • »
      »
      »
      4 years ago, # ^ |
      ← Rev. 2   Vote: I like it +18 Vote: I do not like it

      You should note the assumption that M is prime (that a^(m-2) trick uses Fermat's Little Theorem..)

      → Reply