Have to find LCM of first N numbers where N<=1000. Help me please
→ Обратите внимание
→ Трансляции
→ Лидеры (рейтинг)
| № | Пользователь | Рейтинг |
|---|---|---|
| 1 | Benq | 3792 |
| 2 | VivaciousAubergine | 3647 |
| 3 | Kevin114514 | 3603 |
| 4 | jiangly | 3583 |
| 5 | turmax | 3559 |
| 6 | tourist | 3541 |
| 7 | strapple | 3515 |
| 8 | ksun48 | 3461 |
| 9 | dXqwq | 3436 |
| 10 | Otomachi_Una | 3413 |
| Страны | Города | Организации | Всё → |
→ Лидеры (вклад)
| № | Пользователь | Вклад |
|---|---|---|
| 1 | Qingyu | 157 |
| 2 | adamant | 153 |
| 3 | Um_nik | 147 |
| 3 | Proof_by_QED | 147 |
| 5 | Dominater069 | 145 |
| 6 | errorgorn | 142 |
| 7 | cry | 139 |
| 8 | YuukiS | 135 |
| 9 | TheScrasse | 134 |
| 10 | chromate00 | 133 |
→ Найти пользователя
→ Прямой эфир
Codeforces (c) Copyright 2010-2026 Михаил Мирзаянов
Соревнования по программированию 2.0
Время на сервере: 18.04.2026 11:12:02 (g2).
Десктопная версия, переключиться на мобильную.
При поддержке
lcm(a, b) = a * b / gcd(a, b)
lcm(a, b, c) = lcm(lcm(a, b), c)
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.
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;
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:
The number is greater than actual query: In this case, update actual query and move with query pointer
The first element of TODO-list is equal to number: Multiply answer by the value stored in TODO-list
The Number is not prime: Skip it
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! :)
Thank you, the method is quite understandable and easy to implement.
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
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?
You should note the assumption that M is prime (that a^(m-2) trick uses Fermat's Little Theorem..)
You are 4 years late.
I guess you meant Fermat's Little Theorem, as well.
That was written in 4 AM, Sorry :)
Liorz
Monogorz
When I saw the notification in my mail, I immediately knew what the content would be