Блог пользователя TooNewbie

LCM of first N numbers
Автор TooNewbie, история, 8 лет назад, По-английски

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

  • Проголосовать: нравится
  • +9
  • Проголосовать: не нравится

»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +5 Проголосовать: не нравится

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

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

→ Ответить
»
8 лет назад, # |
← Rev. 3   Проголосовать: нравится +1 Проголосовать: не нравится

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.

→ Ответить
»
8 лет назад, # |
← Rev. 2   Проголосовать: нравится +6 Проголосовать: не нравится

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;

→ Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится +3 Проголосовать: не нравится

    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! :)

    → Ответить
    • »
      »
      »
      8 лет назад, # ^ |
        Проголосовать: нравится +5 Проголосовать: не нравится

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

      → Ответить
  • »
    »
    8 лет назад, # ^ |
      Проголосовать: нравится 0 Проголосовать: не нравится

    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

    → Ответить