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

Автор vanwij, история, 14 месяцев назад, По-английски

Hello Codeforces!

We are excited to invite you to TLX Regular Open Contest #31!

Key details:

Many thanks to:

  • Pyqe and steven.novaryo for their help in coordinating the round and in preparing the problem components.
  • AMnu and joelgun14 for testing the contest.
  • fushar🔥 for the amazing TLX platform.

Please register to the contest and we hope you will enjoy TROC #31!

UPD: Added scoring distribution.

Congratulations to the top 5:

  1. jiangly

  2. maroonrk

  3. heno239

  4. hos.lyric

  5. hitonanode

Congratulations to our first solvers:

You can upsolve the problem here. Editorial is available in the upsolve link!

Thank you for participating and see you on the next contest!

Полный текст и комментарии »

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

Автор vanwij, история, 2 года назад, По-английски

Hello ! I have a problem that goes :

Given $$$N$$$ positive integers $$$A_1, A_2, \dots, A_N$$$. Find $$$LCM(A_1, A_2, \dots, A_N)\text{ }(\text{mod } 1000000007)$$$.

Constraint : $$$1\leq N \leq 10^4,$$$ $$$1\leq A_i \leq 10^9$$$

My approach :

Use sieve to list all primes up to $$$M = \sqrt{A_{max}}$$$. For every prime $$$p$$$ up to $$$M$$$, divide each $$$A_i$$$ by $$$p$$$ as many time as possible (as long as $$$A_i$$$ is divisible by $$$p$$$), and note the largest exponent for each $$$p$$$.

After every $$$A_i$$$ is 'reduced' (divided by all prime up to $$$M$$$), $$$A_i$$$ must be equal to $$$1$$$ or a prime greater than $$$M$$$. Note every distinct final result of $$$A_i$$$. This was done using std::set.

To calculate $$$LCM(A_1, A_2, \dots, A_N)$$$, I used binary exponentiation to calculate the 'contribution' for every small prime $$$p \leq M$$$, and then multiply them with the 'contribution' for large prime, which is equal to the product of all distinct final result of $$$A_i$$$ 's.

However, this approach yields TLE and I cannot figure out a faster way to solve the problem. Any ideas to solve the problem and explanations are appreciated. Thanks in advance.

This problem is from simulation phase of a contest I joined. Both the simulation and the contest itself was over by September 25th, 2021.

Полный текст и комментарии »

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