Hello Codeforces!

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

Key details:

• Contest URL: TLX
• Time: 11th February 2023, 14:05 UTC
• Writer: Drew_, HappyPacMan, Je-O, juancarlovieri, MetalPower, yz_, vanwij, Zanite
• Duration: 135 minutes
• Problems: 8
• Scoring distribution: 100 — 200 — 300 — 400 — 500 — 600 — 700 — 800

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:

• A: JovanB

• B: JovanB

• C: IgorI

• D: jiangly

• E: hos.lyric

• F: jiangly

• G: jiangly

• H: maroonrk

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

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

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.